Lista de probleme 711

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

Cunoscând numărul de ani vizibili și numărul de participanți din fiecare din acești ani, să se răspundă la mai multe afirmații de tipul enunțat mai sus.

Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulțimea {0,1}. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 și invers. El vrea să aplice operația ZET inițial pentru matricea A, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat R, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.

Mihai vă roagă să calculați valorile K și R. Pentru a preciza tipul cerinței, Mihai folosește un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.

ONI 2017, clasa a X-a

#2193 100m

Proba de 100 metri plat este una dintre cele mai populare și prestigioase probe din cadrul oricărui concurs de atletism. Recordul modial al acestei probe este deținut în prezent de sportivul jamaican Usain Bolt cu timpul de 9.58 secunde.
Uneori lupta dintre sportivi este atât de strânsă încât diferențierea dintre atleți se poate face doar cu ajutorul camerelor de luat vederi ce surprind finish-ul atleților. Au existat cazuri când doi sau mai multi atleți au fost declarați la egalitate.

Considerând N atleți, ce participă la o cursă de 100 metri plat, identificați prin numerele 1, 2, …, N, să se scrie un program care determină numărul P al clasamentelor distincte care pot fi obținute după finalizarea cursei. De exemplu, pentru N = 2, se pot obține 3 clasamente distincte: (1,2), (2,1), (1=2); unde (1=2) reprezintă situația când ambii atleți s-au clasat la egalitate.

ONI 2017, clasa a X-a

#2146 doilan

Fie n un număr natural nenul.

Se construiește mulțimea M a tuturor numerelor formate din exact n cifre, numere formate doar cu cifrele 1 și 2.

Scrieți un program care citește numărul natural n și apoi determină cel mai mic număr natural x din mulțimea M cu proprietatea că x este divizibil cu 2n.

#2149 AN

Ana şi Bogdan au inventat încă un joc. Jocul are jetoane, albe şi negre, care iniţial se aşază într-un teanc, într-o ordine oarecare. Numim configuraţie succesiunea culorilor tuturor jetoanelor din teanc (în ordine, începând din vârful teancului). Un jeton alb va fi codificat prin litera A, iar un jeton negru prin litera N.

La o mutare un jucător poate lua din vârful teancului oricâte jetoane consecutive (dar cel puţin un jeton), cu condiţia ca toate jetoanele luate să aibă aceeaşi culoare. Jucătorii mută alternativ, prima la mutare fiind Ana. Jocul va fi câştigat de jucătorul care ia ultimul jeton.

Spunem că un jucător are strategie sigură de câştig dacă el, urmând această strategie, câştigă jocul, indiferent care sunt mutările celuilalt jucător.

Scrieţi un program care citeşte T configuraţii şi determină pentru fiecare dintre cele T configuraţii dacă Ana are strategie sigură de câştig.

#2151 SLang

SLang este o versiune a aplicației Scratch care pune la dispoziție șapte instrucțiuni de tip I1, I2, I3, I4, I5, I6, I7 prezentate în enunț.

Un program corect este o succesiune de instrucţiuni care respectă următoarele reguli:

1. Începe cu o instrucțiune de tip I1 şi se termină cu o instrucțiune de tip I7.
2. Între instrucţiunea de tip I1 şi instrucţiunea de tip I7 vor exista una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.
3. Corpul unei instrucțiuni de tip I4 poate conține una sau două instrucțiuni de mișcare (adică de tip I2 sau I3) și nu poate conține instrucțiuni de alt tip.
4. Fiecare dintre cele două ramuri ale unei instrucțiuni de tip I5 (ramura daca şi ramura daca nu) poate conține una sau două instrucțiuni de tip I2 sau I3 și nu poate conține instrucțiuni de alt tip.
5. Corpul unei instrucțiuni de tip I6 poate conține una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; similar, fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.

Nivelul de imbricare al unui program corect va fi egal cu numărul de instrucţiuni de tip I6 existente în program.

Dat fiind numărul natural K, reprezentând nivelul de imbricare, scrieţi un program care să rezolve următoarele cerinţe:

  1. determină numărul de programe corecte distincte cu nivelul de imbricare K;
  2. determină numărul minim de instrucțiuni și respectiv numărul maxim de instrucțiuni ce pot exista într-un program corect cu nivel de imbricare K.

Orice număr natural mai mare decât 2 poate fi scris ca sumă de numere naturale nenule aflate în ordine strict crescătoare, astfel încât orice termen al sumei, cu excepția primului termen, este un multiplu al termenului precedent din sumă. De exemplu, 27=3+6+18, unde 6 este multiplul lui 3, iar 18 este multiplul lui 6. Cum se dorește o descompunere formată dintr-un număr cât mai mare de termeni, vom obține și descompuneri cu 4 termeni: 27=1+2+8+16, 27=1+2+4+20, 27=1+2+6+18. Dintre cele trei descompuneri cu 4 termeni, descompunerea 27=1+2+4+20 este minimă din punct de vedere lexicografic (1 și 2 sunt la fel în cele trei descompuneri, dar 4 < 6 și 4 < 8). Numărul 30 poate fi descompus 30=2+4+8+16. El are o descompunere tot de lungime 4, dar este mai mare din punct de vedere lexicografic decât oricare dintre descompunerile cu patru termeni ale lui 27 (2 > 1).

Pentru mai multe seturi de date formate din câte două numere naturale A și B, A ≤ B, se cere să se determine, pentru fiecare set una dintre următoarele cerințe:
1. numărul maxim de termeni în care pot fi descompuse numerele din intervalul [A,B] după regula descrisă în enunț;
2. numărul de numere din intervalul [A,B] care pot fi descompuse cu un număr maxim de termeni;
3. numărul din intervalul [A,B] care admite o descompunere cu un număr maxim de termeni, minimă din punct de vedere lexicografic.

ONI 2017, clasa a X-a

Fiind dat un șir V format din N numere întregi V[1], …, V[N], definim o tăietură în poziția pos ca fiind o subsecvență care conține elementul de pe poziția pos. Formal, tăieturile în poziția pos sunt de forma V[k], V[k+1], …, V[pos], …, V[r-1], V[r] pentru orice k, 1 ≤ k ≤ pos și orice r, pos ≤ r ≤ N. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcția MulT(pos) ca fiind numărul de tăieturi în poziția pos care au valoarea 0. Ioana, fiind foarte curioasă din fire, dar și foarte fascinată de această funcție numită MulT, este foarte interesată în a afla rezultatul pentru MulT(i), unde 1 ≤ i ≤ N.

ONI 2017, clasa a X-a

#2068 kpal

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

Lot informatica, Alexandria, 2017

#2062 piese1

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.

Lot informatica, Alexandria, 2017