Lista de probleme 5

Fie N un număr natural format din cifre nenule.

Să se determine suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului N.

Undeva, în deșertul Sahara, ilustrul biolog Sahraa Gaea a conceput și construit un sistem de irigații ingenios, sistem cu care își propune să irige o zonă deșertică dreptunghiulară bogată în nutrienți minerali. Zona deșertică este împărțită în N*M pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcție de comanda primită de la centrul de control al sistemului.

Sistemul de irigare este astfel conceput încât să irige (ude), pe baza unor comenzi automatizate, parcele dreptunghiulare ale regiunii deșertice.

Orice parcelă are laturile paralele cu laturile zonei deșertice și este identificată prin coordonatele colțurilor stânga-sus (x1,y1), respectiv dreapta-jos (x2,y2). La fiecare comandă se specifică parcela care va fi udată și cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.

Un pătrat al zonei deșertice devine fertil dacă acumulează cel puțin Q litri de apă.

Să se determine aria maximă a unei suprafețe conexe fertile. Prin aria unei suprafețe înțelegem numărul de pătrate ce compun suprafața. Orice două pătrate fertile care au o latură comună fac parte din aceeaşi suprafaţă conexă fertilă.

Domino este un joc care utilizează N piese speciale, de formă dreptunghiulară. Pe prima şi pe a doua jumătate a fiecărei piese este inscripţionată câte o cifră de la 1 la 9.

În timpul jocului cele N piese se așează pe tabla joc astfel încât toate cifrele să fie aliniate pe orizontală, iar jucătorul poate acţiona asupra unei piese în două moduri:

• ELIMINARE – piesa este înlăturată de pe tabla de joc;
• ROTIRE – piesa este rotită cu 180 grade, păstrându-și ordinea relativă în raport cu celelalte piese.

Ştiind că în timpul jocului pot fi efectuate cel mult K1 ROTIRI şi exact K2 ELIMINĂRI de piese, determinaţi cel mai mare număr care se poate forma prin scrierea în ordine, de la stânga la dreapta, a cifrelor de pe piesele rămase pe tabla de joc, în urma efectuării operaţiilor permise.

O tablă pătratică este formată din N x N celule pătrate, identice ca dimensiune, grupate pe N linii şi N coloane numerotate de la 1 la N. Din oricare celulă aflată la linia i şi coloana j, se poate face o deplasare doar spre celula vecină (i + 1, j) sau (i, j + 1), dacă aceasta există. În interiorul a M celule ale acestei matrice s-a așezat câte un jeton.

Numim drum pe această tablă, orice succesiune de celule parcurse conform regulii de deplasare descrisă anterior. Lungimea unui asemenea drum este egală cu numărul de celule parcurse.

Cunoscând dimensiunea tablei N, numărul total de jetoane m şi două numere naturale L şi K, să se determine un număr d, reprezentând numărul de drumuri distincte modulo 31607 de lungime L care pornesc din celula (1, 1) şi care conţin fiecare câte K jetoane.

Studenţii Facultăţii de Informatică din cadrul Universităţii din Cluj, au conceput roboţi care şterg praful, plantează copaci, pun gresie, servesc masa, etc.

Botezat „Rosie“, robotul care şterge praful are două braţe ( S – stâng şi D – drept) pe care sunt montate nişte perii ce sunt învârtite cu ajutorul unui motoraş. Braţul robotului este programat să se poziţioneze în dreptul unei suprafeţe, periile învârtite de motoraş parcurg suprafaţa ştergând în acest fel praful de pe ea.

Pentru o demonstraţie, robotul este aşezat în faţa unei etajere cu N rafturi numerotate în ordine, de jos în sus, cu numere de la 1 la N. Braţul stâng ( S ) al robotului este poziţionat în dreptul primului raft iar celălat braţ ( D ) în dreptul celui de-al K-lea raft.

Pentru ştergerea prafului, deplasarea braţelor robotului este programată astfel:

• fiecare braţ se deplasează doar de jos în sus, de la raftul în dreptul căruia este poziţionat la un moment dat, la raftul situat imediat deasupra acestuia;
• din minut în minut, se deplasează doar unul din braţe, se poziţionează în dreptul raftului corespunzător şi şterge praful de pe acesta;
• dacă ambele braţe ajung în dreptul aceluiaşi raft, atunci robotul se blochează şi demonstraţia se încheie fără succes.

Ştiind că demonstraţia se termină în momentul în care braţul drept ( D ) al robotului a ajuns pe ultimul raft al etajerei, scrieţi un program care calculează numărul M de modalităţi diferite în care poate fi programat robotul pentru a asigura succesul demonstraţiei.

Programul va afişa restul împărţirii numărului M la 64997.