Lista de probleme 6

După ce au învăţat la şcoală numerele, Maria si Mihai au început sa se joace cu ele. Maria şi-a ales numărul 3 şi a spus că îi plac toate numerele ce se pot scrie ca sumă de una sau mai multe puteri distincte ale lui 3. De exemplu: 1 = 30, 91 = 34 + 32 + 30, 27 = 33, sunt numere care îi plac Mariei. Numărul 6 = 32 + 32 nu îi place Mariei (32 apare de 2 ori). Mihai, căruia îi place mereu să intre în competiţie cu Maria, a ales numărul 5 şi a zis că îi plac numerele ce se pot scrie ca sumă de una sau mai multe puteri distincte ale lui 5 (aceeaşi regulă ca la numerele care îi plac Mariei, dar folosind numărul 5). Jucându-se pe calculator, au găsit un fişier puteri35.in în care era scris un număr natural nenul n. Imediat, copii s-au gândit să scrie fiecare într-un fişier (pe care de comun acord l-au numit puteri35.out), fiecare, primele n numere care îi plac. Aici a apărut din nou discuţia: în ce ordine le vor scrie. În sfârşit, au căzut de acord să scrie toate cele 2·n numere în ordine crescătoare.

Dându-se un număr natural nenul n, obţineţi în ordine crescătoare toate cele 2·n numere, primele n numere care îi plac Mariei şi primele n care îi plac lui Mihai.

Alibaba trebuie să descopere cifrul care deschide cufărul cu comoara cea mare. Cifrul este foarte greu de găsit. El a descoperit mai multe pietre, fiecare piatră având o altă culoare, pe fiecare piatră fiind scris un număr natural cu cel mult 4 cifre. Alibaba observă că numerele de pe fiecare piatră sunt distincte două câte două. Regula după care se formează cifrul este una foarte simplă, şi Alibaba a reuşit să o obţină destul de uşor: cifrul este format din alăturarea într-o anumită ordine a tuturor pietrelor. Ceea ce Alibaba mai ştie este că pe poziţia p din cifru se găseşte cu siguranţă cifra k.

Scrieţi un program care determină numărul de variante de cifruri pe care va trebui să le încerce Alibaba. Numărul fiind foarte mare se va calcula modulo 46337.

Ionică a strâns foarte multe CD-uri cu jocuri, muzică, filme, etc. pe care le are aşezate în n cutii, codificate prin 1, 2, …, n. Pe la Ionică vine în vizită vărul lui, Florin, care tocmai câştigase un concurs de matematică. Ca să-i mai taie din elan, Ionică îi propune lui Florin să pună o parte din CD-uri într-o ladă mai mare, astfel încât să se ia din fiecare cutie cel puţin câte un CD şi la sfârşit să rămână în fiecare cutie cel puţin un CD.

Pentru a complica problema, Ionică nu îi spune lui Florin câte CD-uri sunt în fiecare cutie, ci îi spune că are în total S CD-uri şi că, dacă ia din fiecare cutie un număr de CD-uri şi le pune în altă cutie va obţine în final acelaşi număr de CD-uri în toate cutiile.

Să se scrie un program care cunoscând n, S şi numărul de CD-uri mutate din fiecare cutie, determină numărul k de modalităţi distincte de introducere a CD-urilor în ladă, respectând regula din enunţ.

Maria este pasionată de matematică. Ea este interesată în special elementele şirului Fibonacci şi vrea să studieze proprietăţile elementelor acestui şir. De curând a scris elementele Fibonacci: 1, 1, 2, 3, 5, 8, 13, … şi a observat că un element, numărul 5, poate fi scris ca sumă de alte două numere Fibonacci ridicate la pătrat, 5=12+22, iar alt număr Fibonacci, numărul 144, poate fi scris ca diferenţă a altor două numere Fibonacci ridicate la pătrat, 144=132-52.

Maria a fost încântată de rezultatele pe care le-a obţinut şi ar dori să mai găsească şi alte elemente ale şirului care se pot scrie ca sumă sau ca diferenţă de alte două numere Fibonacci ridicate la pătrat.

Ajutaţi-o pe Maria, să decidă despre un element Fibonacci oarecare dacă se poate scrie ca sumă sau diferenţă de două numere Fibonacci distincte ridicate la pătrat. Datorită valorilor mari ale numerelor Fibonacci se cere restul împărţirii lor la 46337.

Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.

Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.

Cunoscând dimensiunea m*n a tablei de şah, respectiv poziţia iniţială (l1,c1) şi poziţia finală (l2,c2) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.