Lista de probleme 45

Filtrare

Dificultate

Operații intrare/ieșire

#1924 QStiva

Se dă o stivă inițial vidă. Să se efectueze Q operații de forma:

1 x: Se adaugă x în stivă.
2: Se șterge elementul din vârful stivei.
3 S: Se întreabă dacă se poate scrie valoarea S ca sumă de elemente aflate în stivă. Fiecare element poate fi folosit o singură dată în calcularea sumei. Răspunsul va fi 1 în caz afirmativ și 0 în caz negativ.

Se dă un vector cu n elemente, numere naturale. Fie două numere x și y, cu proprietatea că 1 ≤ x , y ≤ n. Scrieți un program care răspunde la m întrebări de tipul “Care este elementul minim din intervalul [x , y]?”.

Să se găsească cel mai mare divizor comun al unui set de numere Fibonacci.

Zoli și D’Umbră se pierd din nou prin labirint.

Tractor Runda II

#1248 carti2

Un filipinez cultivat are X cărți pe care dorește să le vândă.

Tractor Runda II

Ajutați-l pe vrăjitorul Arpsod să găsească aria maximă unei suprafețe de înălțime maximă, după căderea ploilor de meteoriți.

Se dă un vector indexat de la 1 cu n elemente numere naturale. Să se răspundă la q întrebări de forma x y, cu semnificația: “Care este cel mai mare divizor comun al elementelor cu indici cuprinși între x și y, inclusiv?”

#1675 Calc

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cunoscând N, să se determine:

  1. Numărul de zile modulo 1000000007 în care se desfășoară concursul.
  2. Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.

ONI 2016, clasa a X-a

#1677 Tort

Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la 1 la N pentru linii și de la 1 la M pentru coloane. Tortul este format din bucăți de dimensiune 1x1, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel mai mare pătrat care conține bucăți acoperite cu același tip de glazură. În cazul în care există mai multe astfel de felii, NN o alege pe cea care are colțul din dreapta jos situat pe linia cu indicele cel mai mic. Dacă și în acest caz există mai multe posibilități, el o va alege pe cea cu colțul din dreapta jos situat în coloana cu indicele cel mai mic.

Precizați latura și coordonatele colțului din dreapta jos pentru fiecare felie de tort primită, în ordinea specificată mai sus.

ONI 2016, clasa a X-a

#1689 MoveDel

Se consideră două șiruri de caractere A și B, ambele șiruri având același număr de caractere.

Asupra șirurilor se aplică următorul algoritm:

  • șirul A se permută circular cu ki poziții spre stânga
  • din cele două șiruri se elimină caracterele care coincid din punct de vedere al poziției și valorilor

Algoritmul se oprește când fie ambele șiruri devin vide, fie șirurile nu mai au caractere comune. Valoarea ki pentru fiecare pas i reprezintă al i-lea număr prim din mulțimea numerelor prime.

Dându-se N și M, să se genereze șirurile A și B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două șiruri să fie M.

ONI 2016, clasa a X-a