Lista de probleme 1991

David este mare zugrav și nu se duce nicăieri fără trafaletul său magic. El are la dispoziție o matrice A cu N linii și M coloane, care este colorată în alb și negru, asemenea unei table de șah. Fiecare celulă a matricei conține o valoare asociată. David vopsește o submatrice cu alb sau negru la alegere. Trafaletul adună automat (pentru că este magic) valorile din celulele vopsite care nu își schimbă culoarea, și scade valorile din celulele vopsite care își schimbă culoarea. Rezultatul acestui calcul este punctajul lui David. Cum David nu a reușit până acum să combine zugrăvitul și programarea, vă roagă pe voi să îl ajutați să obțină punctajul maxim!

Se cunosc înălțimile a N vârfuri, plasate de la stânga la dreapta, în cadrul unui lanț muntos. Dacă plasăm o santinelă pe un vârf de o anumită înălțime, aceasta veghează vârful respectiv și maximum K vârfuri la stânga și maximum K vârfuri la dreapta acestuia, dar cu condiția ca înălțimile acestor vârfuri vegheate să fie mai mici sau egale cu înălțimea vârfului pe care se află santinela. Date fiind N, K și înălțimile celor N vârfuri, să se determine:

• Numărul maxim de vârfuri consecutive, începând de la primul vârf al lanțului muntos (inclusiv acest vârf), ce pot fi vegheate cu o singură santinelă.
• Numărul minim de santinele necesare ca toate vârfurile să fie vegheate.

Macarie a primit o nouă temă la informatică, având următorul enunț: Se consideră un șir de numere naturale nenule, A cu N elemente. Fie șirul crescător D format din toți divizorii naturali, nu neapărat distincți, ai elementelor din A. De exemplu, pentru N = 4 și A = (6,2,3,2), avem șirul D = (1,1,1,1,2,2,2,3,3,6). Cunoscându-se un șir Poz format din Q numere naturale nenule, reprezentând poziții din șirul D să se determine, pentru fiecare dintre acestea, elementul corespunzător din șirul D.

Pentru un șir de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte. Un exemplu de astfel de secvență este: 9 1 0, dar un exemplu de secvență care nu respectă această regulă este 4 2 1 3 4. Dându-se t șiruri a de n numere, să se găsească lungimea celei mai lungi secvențe care conține maximum 3 numere distincte.

Se considera n numere și o cifră nenulă k. Să se calculeze suma cifrelor numerelor dintre cele n citite care incep cu cifra k.

Un număr se numește “nice” dacă conține 69 ca subsecvență. În alte cuvinte, dacă în numarul respectiv, imediat după o cifra 6 se află o cifră 9, numărul respectiv este “nice”.

De exemplu, numărul 369420 este “nice”, pe când numărul 684920 nu este “nice”.

Se dau N numere naturale. Să se determine câte dintre ele sunt “nice”.

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.

Î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.

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.