Lista de probleme 972

Filtrare

#1621 Miting

În Orașul Liniștit un număr de k tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceștia este mare, ei se vor deplasa spre punctul de întâlnire cu mașinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulțimea A ... Z. Nu există două pancarte cu litere identice. Cele k litere formează un cuvânt, să-l notăm cuv, cunoscut.

Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu n*m zone pătratice, dintre care unele sunt interzise. Se știe că o mașină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină și nu consumă combustibil dacă staționează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două mașini se întâlnesc într-o zonă și toate literele aflate în cele două mașini reprezintă o secvență din cuvântul cuv, atunci ei vor continua drumul cu o singură mașină, luând desigur toate pancartele cu ei. În caz contrar, mașinile își continuă drumul separat.

De exemplu, dacă cuvântul cuv este JOS, atunci mașina care transportă litera J poate prelua tânărul care aduce pancarta cu litera O, sau invers: mașina având litera O poate prelua tânărul care aduce litera J. Apoi se poate continua drumul spre mașina care transportă litera S. În altă variantă se pot reuni mai întâi literele S și O într-o singură mașină, dacă mașinile care le transportau se întâlnesc în aceeași zonă. Totuși, între mașina care transportă doar litera J și cea care transportă doar litera S nu se poate realiza un transfer, adică o reunire a literelor.

Cunoscând dimensiunile cartierului n și m, cuvântul cuv, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:

  1. Aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.
  2. Numărul minim de unități de combustibil consumați de către toate mașinile, știind că în final toți tinerii se vor reuni într-o singură mașină.

Se consideră o mulțime S care conține N șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea S conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Fiind dată o mulțime S formată din N șiruri de caractere se cere:

  1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
  2. Să se determine toate șirurile interesante din mulțimea S.

OJI 2016, Clasa a X-a

#865 Palat

Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din n*m camere, dispuse sub forma unei matrice cu n linii și m coloane.

În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă cameră dacă se învecinează pe linie sau pe coloană. În una dintre camere se află Ileana Cosânzeana, iar în alte camere se afla câte un Făt-Frumos. Aceștia pot trece dintr-o cameră în alta, cu condiția să nu intre într-o cameră care conține un zmeu. Trecerea dintr-o cameră în alta a unui Făt-Frumos durează un minut.

Alegerea celui care va primi mâna Ilenei se face pe principiul primul venit, primul servit (suntem la capitolul Coada). Mai precis, se va căsători cu Ileana Cosânzeana acel Făt Frumos care ajunge primul la ea. Dacă ajung la Ileana Cosânzeana mai mulți Feți-Frumoși în același timp, deoarece este interzisă poligamia, Ileana se va căsători cu Făt-Frumos care la început era situat cât mai jos (pe o linie cu indice cât mai mare) și cât mai la dreapta (pe o coloană cu indice cât mai mare).

Aflați poziția inițială a lui Făt-Frumos care va primi mâna fetei.

Se consideră un șir de caractere format numai din litere mici ale alfabetului englez. Dacă șirul conține subșiruri consecutive care se repetă, el poate fi scris condensat. De exemplu, șirul mamateteter poate fi scris (ma)2(te)3r – subșirul care se repetă se scrie între paranteze rotunde, urmat de numărul de apariții.

Dându-se un șir în forma condensată, să se determine șirul în forma inițială.

#1600 s_p_c_2

Scrieţi un program care citeşte din fişierul de intrare şiruri de caractere de forma tip#cuvânt, unde cuvânt este un şir oarecare de litere iar tip poate fi una din literele S, P sau C, semnificaţia fiind subiect, predicat sau complement. Programul va afişa, în ordine lexicografică, toate propoziţiile având structura subiect predicat complement ce pot fi formate cu ajutorul cuvintelor citite. Datele de intrare se consideră a fi corecte.

Admitere Informatica Iasi, 2012 - varianta modificată

#1598 Coada1

Se consideră C o coadă de numere naturale, iniţial vidă. Se definesc 2 tipuri de operaţii.

Operaţia 1 : push X, adaugă elementul X în coadă. Dacă X există deja în coadă, se scot toate elementele din coadă, pana la întâlnirea lui, inclusiv X.

Exemplu: 
	C: 2 4 5 1 6
	Push 5
	C: 1 6 5 ( s-au scos 2, 4, 5).

Operaţia 2: query X, cere afişarea poziţiei elementului X în coada C. Dacă elementul nu există în coadă, se afişează -1.

Exemplu:
	C: 2 5 1 3 7
	Query 1
	Răspuns: 3

#1562 Abba

Pentru transmiterea unui mesaj format exclusiv din litere mici ale alfabetului englez, se utilizează un aparat electronic care are anumite limitări tehnice. Astfel, el poate transmite mesaje formate doar din litere vecine din alfabet sau formate din aceeași literă. De exemplu mesajul: defffedcbab poate fi transmis, iar mesajul accded nu poate fi transmis deoarece literele a și c nu sunt vecine în alfabetul englez.

Din acest motiv mesajul ce urmează să fie transmis trebuie codificat pentru a fi compatibil cu aparatul.

Pentru codificare, mesajul este prelucrat în etape până satisface limitările aparatului. O etapă de prelucrare presupune inserarea între fiecare două litere vecine ale mesajului a literei mijlocii. Litera mijlocie este acea litera situată la jumătatea secvenței din alfabet ce are capete literele vecine. Dacă nu există se ia în considerare litera mai mică.

Determinați numărul de etape de prelucrare necesare pentru codificarea mesajului și lungimea finală a mesajului.

Olimpiada Locală de Informatică, Timișoara, 2016

#1580 schimb

Se dau trei numere naturale n, k și p și n șiruri formate din litere mici ale alfabetului englez. Înlocuiți a k-a literă din fiecare șir cu a p-a literă din alfabet. Dacă șirul are mai puțin de k litere se va scrie oglinditul lui.

#1576 zona3

Se consideră o matrice cu n linii și m coloane. Spunem că o poziție este liberă dacă elementul de pe linia i și coloana j este egal cu 0 și 1 în caz contrar. Spunem despre mai multe elemente ocupate că formează o zonă, daca elementele se învecinează pe cele patru direcții (sus, jos, dreapta, stânga).

Calculați pentru fiecare zonă numărul de elemente și afișați noua matricea formată prin înlocuirea elementelor egale cu 1 cu numărul de elemente pe care îl are zona din care face parte elementul respectiv.

#1388 Colecție C++

Ajută-mă, te rog!”, spune Dudu. El vă cere să aflați care este numărul de vederi unice din colecția sa.

Olimpiada de Informatica, etapa pe Scoala, CNITV