Lista de probleme 12

Un număr natural se numește kpower dacă este putere a numărului natural k. O secvență kpower este un subşir de numere kpower care apar pe poziţii consecutive într-un şir. Fiind dat un un număr natural k și un şir de n numere naturale, scrieți un program care rezolvă următoarele cerințe:
1. Determină cel mai mare număr kpower dintre cele n numere date.
2. Determină lungimea maximă a unei secvențe kpower.
3. Determină cea mai mare sumă ce se poate obține adunând numerele dintr-o secvență kpower de lungime maximă.

Ștefan trebuie să verifice dacă Ana, sora lui mai mică, a înțeles corect conceptul de triunghi echilateral și îi propune o temă. În prima zi Ana trebuie să deseneze un triunghi echilateral T0 cu latura 1. A doua zi ea trebuie să deseneze un triunghi echilateral cu latura 2 și, apoi, în fiecare zi trebuie să deseneze un nou triunghi echilateral având latura mai mare cu 1 decât latura triunghiului din ziua precedentă. Scrieţi un program care, pentru un număr natural n dat, să determine:
1. Câte triunghiuri elementare T0 au fost desenate în n zile.
2. În ce zi a fost desenat și pe ce nivel se afla al n-lea triunghi elementar T0 desenat de Ana.
3. Câte triunghiuri elementare T0 sunt etichetate cu numere prime în primele n zile.

La atelierul de făcut potcoave lucrează N muncitori, numerotaţi pentru simplitate de la 1 la N. Fiecare muncitor a încheiat la angajare un contract în care este specificat numărul de potcoave pe care trebuie să le producă muncitorul în fiecare zi de muncă, respectiv a câta zi muncitorul este liber. Mai exact, muncitorul i (1 ≤ i ≤ N) trebuie să producă în fiecare zi de muncă pi potcoave, iar fiecare a ki-a zi va fi liberă (adică muncitorul i va fi liber în ziua ki, 2ki, 3ki, …). În ziua liberă el nu va veni la atelier, deci nu produce potcoave. Atelierul tocmai a primit o comandă de M potcoave. Scrieţi un program care să determine numărul minim de zile după care comanda poate fi integral livrată.

Fotbalul este considerat sportul rege, având aproximativ 3,5 miliarde de fani. Printre acești fani se numără și un copil pe nume Messi, care are doar șase ani. Prietenul lui Ronaldo, cu doi ani mai mare l-a învățat atât regulile jocului, cât și cum se calculează punctajul echipelor din ligă. Ronaldo i-a explicat că pentru fiecare meci câștigat echipa primește 3 puncte, pentru fiecare meci pierdut echipa nu primește niciun punct, iar pentru meciurile terminate la egalitate, echipa primește 1 punct. După ce-i explică regulile, Ronaldo vrea să verifice dacă Messi a înțeles pe un exemplu. Cunoscând numărul de echipe și pentru fiecare echipă numărul de meciuri câștigate, numărul de meciuri pierdute și numărul de meciuri încheiate la egalitate, determinați, în funcție de paritatea lui n două rezultate: dacă numărul de echipe este par să se afle cel mai bun punctaj dintre toate echipele, iar dacă numărul de echipe este impar să se afle care este cel mai mic număr de meciuri pierdute.

Instalatorul Mario a plecat în căutarea prințesei Peach. Până a ajunge la Castelul lui Bowser, acolo unde era ținută prizonieră prințesa, Mario a adunat N monede magice. Fiecare monedă, numerotată de la 1 la N are o o anumită valoare, moneda i având valoarea mi (1 ≤ i ≤ N). Ajuns la Castel, Mario l-a întâlnit pe Bowser care era mândrul posesor a unei colecții impresionante de monede, numerotate de la 1 la M, moneda i având o valoare bi (1 ≤ i ≤ M). În confruntarea finală, Bowser îi oferă lui Mario șansa de a o salva pe Peach doar dacă reușește să facă schimburile necesare între monedele lor, astfel încât cele mai mici N monedele să fie în posesia lui Mario și cele mai mari M valori să fie în posesia lui Bowser. Scrieți un program care să îi permită lui Mario să o salveze pe Peach.

Piticul Doc și-a securizat pin-ul cardului bancar într-un mod cunoscut doar de el. Pin-ul este format din exact 4 cifre. Doc dispune de o mulțime de informații numerice dispuse pe R rânduri. Fiecare cifră din pin-ul cardului bancar este un element majoritar pe rândul său, adică numărul de apariții ale cifrei respective este mai mare decât n / 2, unde n reprezintă numărul total de cifre de pe rândul respectiv. Tu poți afla pin-ul lui Doc sau crezi că a greșit securizarea pin-ului? Cunoscând numărul R de rânduri și numerele de pe fiecare rând, scrieţi un program care să determine pin-ul lui Doc.

Cunoscând numărul N de numere și numerele scrise la început de Liisa pe foaia de hârtie, scrieţi un program care să rezolve următoarele două cerinţe:
1. Determină numerele rezultat obținute de Liisa, pentru cele N numere.
2. Determină cel mai mare dintre numerele imagine obținute și numărul său de apariții în șirul celor N numere imagine.

Alexandru și Tudor au inventat un joc numit Jocul Divizorilor. La acest joc, fiecare dintre cei doi jucători extrage un șir format din n numere. Alexandru este jucătorul cu numărul 1 si Tudor este jucătorul cu numărul 2. Pentru fiecare număr x din șir, se obține divizorul său prim care are puterea cea mai mare denumit p-divizor; dacă numărul x are mai mulți divizori primi care au aceeași putere maximă, atunci p-divizorul este divizorul prim cel mai mare dintre aceștia. Astfel, p-divizorul numărului 36 este 3, p-divizorul numărului 12 este 2, p-divizorul numărului 30 este 5. Scrieţi un program care citește numărul n, cele n numere din șirul lui Alexandru, apoi cele n numere din șirul lui Tudor și determină numărul de ordine al câștigătorului jocului, punctajul câștigătorului jocului și cel mai mare număr dintre toate numerele câștigătoare din joc.

În Ajunul Crăciunului, așteptându-l nerăbdători pe Moș Crăciun, Andrei și Bogdan se hotărăsc să joace un joc, căștigătorul jocului fiind primul care va primi cadoul de la acesta. Ei scriu pe n bilete n numere naturale, câte un număr pe fiecare bilet. Fiecare extrage câte un bilet dintr-un bol. Un bilet este norocos dacă numărul scris pe el este număr fantastic. Un număr este fantastic dacă are număr par de cifre și este multiplu de 2024. Câștigătorul jocului este cel care extrage cele mai multe bilete norocoase. Dacă la finalul jocului cei doi băieți au extras număr egal de bilete norocoase sunt amândoi considerați câștigători și vor primi cadoul în același moment de timp. Cunoscând numărul n de bilete precum și numerele scrise pe cele n bilete, determinați care este numărul total de bilete norocoase extrase de cei doi copii.

Ana și Bogdan sunt pasionați de criptarea mesajelor. Ei au studiat mai multe metode de criptare. Ultimul algoritm pe care l-au studiat presupune să scrie un cuvânt cu litere mari ale alfabetului englez. Apoi, sub acest cuvânt să scrie toate permutările sale circulare cu o poziție spre stânga obținând astfel o matrice de caractere. Ordonează lexicografic liniile matricii, memorează ultima coloană și adaugă la finalul șirului astfel obținut numărul liniei pe care a ajuns cuvântul inițial, șirul rezultat fiind denumit cript-ul șirului inițial. Analizând matricea de caractere obținută ei au observat că în matrice se obțin submatrici cu proprietatea că în cele patru colțuri ale lor se află același caracter. Să se scrie un program care citește un număr natural c, reprezentând cerința care trebuie să fie rezolvată, apoi citește un cuvânt. Programul rezolvă următoarele cerințe:
1. Dacă c = 1, șirul citit este un cuvânt necriptat, programul va determina și va afișa cript-ul obținut conform algoritmului descris anterior.
2. Dacă c = 2, șirul citit este un cript, programul va determina și va afișa cuvântul necriptat.
3. Dacă c = 3, șirul citit este un cuvânt necriptat, programul va determina matricea de caractere obținută conform algoritmului descris anterior și va afișa numărul maxim de elemente dintr-o submatrice cu proprietatea că în colțurile sale se află același caracter.