Lista de probleme 974

Alina este pasionată de rebus şi literatură. Recent, a citit un articol în limba engleză despre fraze denumite pangram. O frază pangram este formată din cuvinte, separate printr-un singur caracter (spaţiu sau virgulă) şi care folosește fiecare literă din alfabetul unei limbi cel puțin o dată.
O frază pangram perfectă este o frază pangram care folosește fiecare literă din alfabet doar o singură dată. Alina se decide să stabilească frazele pangram, numărul de fraze pangram şi numărul de fraze pangram perfecte dintr-un text. Fiecare frază din text începe cu o literă mare şi se încheie cu caracterul punct.

Scrieţi un program care să determine numărul de fraze pangram, numărul de fraze pangram perfecte dintr-un text dat şi să afişeze frazele pangram în ordine lexicografică.

În livada sa, Vasile are pomi fructiferi, organizaţi în parcele în funcţie de soi. În fiecare an, scoate la vânzare doar o parte dintre pomii adulţi dintr-o singură parcelă. Ca să asigure spaţiu de dezvoltare pentru pomii rămaşi, Vasile s-a decis să fie scoşi la vînzare numai acei pomi din parcelă al căror număr de ordine este divizibil cu o cifră k, numită cifra anului.

Cunoscând valorile a şi b, reprezentând numerele de ordine ale primului, respectiv ultimului pom din parcela din care se face vânzarea, precum şi k – cifra anului, se cere să se determine numărul de pomi scoşi la vânzare de Vasile în acest an.

• n – prin care primește un număr natural
• a – prin care primește un tablou unidimensional cu n elemente, numere naturale din mulțimea {1,2,3}.

Subprogramul ordonează crescător tabloul a fără a returna valori.

Se dă un număr natural n. Să se genereze o matrice pătratică de ordinul 3n, cu elemente din mulțimea {0, 1}, după modelul covorului lui Sierpinski.

Se citesc numere până când nu mai este niciun număr de citit. Se cere să se afișeze valoarea maximă dintre acestea.

Inspiraţi de clasicul joc Tic-Tac-Toe (X şi 0), Teodora şi Ştefan îşi propun să joace ceva asemănător, adăugând jocului clasic câteva reguli noi:

• tabla de joc este un pătrat de latură N, care este împărţit în N*N celule, aşezate pe N linii şi N coloane; celulele pătratului sunt numerotate de la 1 la N2 parcurgând liniile de sus în jos, și coloanele de la stânga la dreapta;
• Teodora va marca celulele cu X (litera X), iar Ştefan cu 0 (cifra 0);
• în cadrul unei runde, copiii marchează alternativ câte o celulă din pătrat, nemarcată anterior;
• o rundă a jocului este descrisă printr-un șir format din exact N2 numere naturale reprezentând celulele pătratului, în ordinea în care au fost marcate succesiv de cei doi copii;
• jocul are K runde; prima este începută de Teodora, a doua de Ştefan, a treia Teodora, a patra Ştefan şi aşa mai departe;
• o rundă este câştigată de jucătorul care reuşeşte primul să marcheze complet o linie, o coloană, diagonala principală sau una din cele două semidiagonale paralele şi alăturate cu aceasta, diagonala secundară sau una din cele două semidiagonale paralele şi alăturate acesteia;
• o rundă se încheie fără un câştigător dacă după marcarea celor N2 celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu acelaşi simbol.

Cunoscând numerele N, K şi cele K şiruri de numere care reprezintă rundele jucate, scrieţi un program care să rezolve una dintre următoarele două cerinţe:

1. Să se determine câte runde a câştigat fiecare copil.
2. Să se determine care este cel mai mare număr de marcări efectuate până la câştigarea unei runde.

Alecu este un copil năzdrăvan care strică orice lucru. El a scris pe o foaie de hârtie un cuvânt. Fiind elev în clasa întâi, el nu a învățat decât primele X litere mici ale alfabetului englez, iar cuvântul de pe foaie este scris doar cu aceste litere.

El își propune să taie foaia în mai multe bucăți dar să obțină doar cuvinte având același număr de litere și în același timp toate cuvintele obținute în urma tăierii să fie palindromuri. Un cuvânt este palindrom dacă citit de la stânga spre dreapta este identic cu cuvântul obținut prin citire de la dreapta spre stânga. Exemplu de palindrom este cuvântul abcba.

În dorința de a obține în urma tăierii doar cuvinte palindrom, Alecu poate schimba orice literă a cuvântului, în oricare alta cunoscută de el, dar fiecare astfel de schimbare are un cost cunoscut. Mai mult, el știe că o literă din cuvântul inițial nu o poate schimba decât cel mult o singură dată.

Notăm cu Nr(c) numărul minim de palindromuri de lungimi egale în care poate fi tăiat cuvântul de pe foaie, având voie să se efectueze schimbări ale literelor, dar care să nu însumeze un cost total mai mare decât c. Alecu știe să determine valoarea Nr(c) pentru orice număr natural c.

Scrieți un program care pentru un număr natural Q și șirul numerelor naturale 0,1,2,...,Q-1,Q, determină suma: Nr(0)+Nr(1)+Nr(2)+...+ Nr(Q-1)+Nr(Q).

Ion este un tânăr muzician și studiază chitara clasică. La un spectacol în aer liber, Ion a fost invitat să interpreteze câteva dintre piesele sale. Ion are în repertoriu n piese, a căror durată este t[1], t[2], …, t[n] și ştie că timpul care-i va fi alocat nu poate depăşi T unităţi de timp. Pentru alegerea pieselor, Ion este interesat să ştie câte variante distincte are de a interpreta cel puţin o piesă în spectacol, astfel încât durata totală a pieselor interpretate să nu depăşească T. Două variante sunt distincte dacă există cel puţin o melodie care se găseşte într-o variantă şi nu se găseşte în cealaltă variantă. Cunoscând n, T și duratele pieselor, determinaţi numărul de variante distincte pe care le are Ion de a interpreta piese astfel încât durata lor să nu depăşească T.

Se consideră o tablă de șah sub forma unei matrice cu M linii si N coloane conținând caracterele '.' si '#'. Celulele care conțin '#' sunt considerate interzise și nu se pot așeza turnuri în ele. Celulele interzise nu blochează atacurile turnurilor. Să se calculeze X, numărul de posibilități de a așeza turnuri în celulele neinterzise, astfel încât să nu existe doua turnuri așezate pe aceeași linie sau pe aceeași coloana. Deoarece acest număr poate fi foarte mare, se va determina X modulo 1000003.

După ce a luat aur la ONI2017, Roby băiatul de aur a decis să ajute la construcția tării Zoomba. Zoli astfel i-a cerut să se ocupe de construirea unui acoperiș ce va acoperi toată țara. Acesta va fi alcătuit din grinzi ce se vor sprijini pe puncte în sistemul cartezian. O grindă va uni două puncte. Acoperișul trebuie construit în așa fel încât, privit de sus, orice unghi format de către două grinzi consecutive să fie ≥ 180 (în cazul în care plouă, nu se dorește ca acesta să țina apa) și să acopere toate punctele de sprijin. Din când în când, Zoli este interesat de aria poligonului format din totalitatea punctelor ce se află sub acoperiș și deasupra axei OX. Astfel se disting următoarele evenimente:

1 x y: Se adaugă punctul de coordonate întregi (x, y) în plan. De acum încolo, se vor putea așeza grinzi pe acesta.
2: Zoli întreabă care este aria poligonului descris mai sus.