Lista de probleme 4

Generaţi un tablou bidimensional cu proprietăţile:

• conţine N linii şi N coloane;
• elementele sale sunt numere naturale nenule;
• suma elementelor este egală cu numărul natural nenul S;
• pe nici o linie şi pe nici o coloană nu există două elemente identice;
• diferenţa dintre cel mai mare şi cel mai mic element ale tabloului este minimă.

O proprietate interesanta a fracțiilor ireductibile este ca orice fracție se poate obține după următoarele reguli:
- pe primul nivel se afla fracția 1/1;
- pe al doilea nivel, în stânga fracției 1/1 de pe primul nivel, plasam fracția 1/2 iar în dreapta ei fracția 2/1;

nivelul 1: 1/1
nivelul 2: 1/2 2/1

- pe fiecare nivel k se plasează sub fiecare fracție i / j de pe nivelul de deasupra, fracția i / (i + j) în stânga, iar fracția (i + j) / j în dreapta.

nivelul 1: 1/1
nivelul 2: 1/2 2/1
nivelul 3: 1/3 3/2 2/3 3/1

Dându-se o fracție oarecare prin numărătorul și numitorul său, determinați numărul nivelului pe care se află fracția sau o fracție echivalentă (având aceeași valoare) cu aceasta.

La o competiție au participat N concurenți. Fiecare dintre ei a primit un număr de concurs astfel încât să nu existe concurenți cu același număr. Numerele de concurs aparțin mulțimii {1,2,...,N}. Din păcate, clasamentul final a fost pierdut, iar comisia își poate aduce aminte doar câteva relații între unii participanți (de genul “participantul cu numărul 3 a ieșit înaintea celui cu numărul 5”). Șeful comisiei are nevoie de un clasament final și vă cere să-l ajutați determinând primul clasament în ordine lexicografică ce respectă relațiile pe care și le amintește comisia.

Un fermier are un teren care are forma unui tablou dreptunghiular de N x M unități. Pe teren sunt plantați din loc în loc copaci, pe care fermierul nu dorește sa-i taie. Dorind să-și supravegheze cultura, fermierul realizează un mic robot de forma pătrată având latura de 3 unități pe care îl poate teleghida prin fermă, parcurgând unitate cu unitate o anumită suprafață. Robotul se poate mișca pe verticală și pe orizontală dar nu poate trece peste copaci, nu îi poate distruge, nu se poate roti și are nevoie pentru mișcare de o suprafață corespunzătoare dimensiunii lui. Ajutați-l pe fermier sa determine suprafața maxima pe care o poate urmări, folosind acest sistem.