Lista de probleme 972

Filtrare

Se consideră un text alcătuit din mai multe linii, în care cuvintele sunt separate prin spatii și caractere din setul .,;:-?!. Să se determine cuvintele distincte din text care conţin subşirul ate, fără a face distincţie între litere mari şi mici.

Find dat un string S, se poate obține un palindrom din șirul inițial ștergând doar un singur caracter ?

Concursul Interjudețean de Informatică „Memorial Ștefan Dârțu”, ediția a XI-a, 12 decembrie 2015, Vatra Dornei

#2195 sumpow2

Orice număr natural nenul se poate scrie în mod unic ca o sumă de puterile ale lui 2 care nu se repetă. Exemplu: 77 = 20 + 22 + 23 + 26.
Primele 16 puteri ale lui 2 se reprezintă prin litere ale alfabetului englez, după cum urmează: a = 1, b = 2, c = 4, d = 8, e = 16, f = 32, g = 64, h = 128, i = 256, j = 512, k = 1024, l = 2048, m = 4096, n = 8192, o = 16384, p = 32768.
Astfel, orice număr din intervalul [1, 216] poate fi codificat ca o combinație unică a acestor litere, aranjate în ordine alfabetică, în care orice literă apare cel mult o singură dată, astfel încât suma valorilor acestor litere să fie egală cu valoarea numărului (77 = acdg).

Să se scrie un program C/C++ care citește două șiruri de caractere ce reprezintă două numere naturale codificate după regula de mai sus, program care afișează un șir de caractere ce reprezintă suma celor două numere.

#3392 magazin

Se cere să se determine numărul minim de litere (lungimea celui mai scurt prefix) de care are nevoie fiecare dintre prieteni pentru a-și construi numele.

Scrieți definiția completă subprogramului C++ citmat care citește de la tastatură dimensiunile și elementele unui tablou bidimensional.

Scrieți definiția completă subprogramului C++ afismat care afișează pe ecran elementele unui tablou bidimensional.

#1676 Elmer

În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze rațe în orașul său preferat, Craiova. Se știe că există N rațe reprezentate prin puncte în planul de coordonate xOy, având coordonatele (x,y) și M ziduri sub forma unor segmente verticale având un capăt pe axa Ox și o anumită înălţime fiecare.

Vânătorul Elmer dorește să împuște cât mai multe rațe. El poate fi poziționat în orice punct de abscisă număr natural nenul, pe axa Ox. O rață poate fi ochită de vânător dacă zidul nu blochează glonțul vânătorului, adică segmentul imaginar delimitat de rață și de vânător nu se intersectează cu nici un zid.

Să se afle numărul maxim de rațe care pot fi ochite de vânătorul Elmer.

ONI 2016, clasa a X-a

#1690 Undo

XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere a=(a[1], a[2], … ,a[N]) și N numărul de elemente din șir după fiecare operație.

Astfel el are de realizat următoarele operații pornind de la un șir vid:

  • Inserează la sfârșitul șirului o valoare x;
  • Șterge ultimele x elemente din șir;
  • Readaugă la sfârșitul șirului primele x elemente șterse. Dacă, de exemplu, în operația anterioară de ștergere a unui număr y de elemente, am șters elementele a[N-y+1], a[N-y+2],…, a[N], iar acum urmează o operație de readăugare a x elemente, vor fi adăugate în ordine elementele a[N-y+1], a[N-y+2],…, a[N-y+x] la sfârșitul șirului.

Din când în când XORin își pune următoarea întrebare: de câte ori există valoarea x în șir?

#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