Lista de probleme 974

Scrieţi un program care citeşte din fişierul de intrare mai multe şiruri de caractere formate din litere mici ale alfabetului englez şi determină câte dintre acestea sunt formate din două şiruri identice (cu lungimea cel puţin 1) concatenate.

Anul 2154, undeva pe luxurianta planetă Pandora.

Aici coloniștii RDA (Resources Development Administration) doresc să-și stabilească o bază stelară pentru a exploata rezervele naturale de unobtainium, un minereu rar și prețios aflat din belșug pe munții plutitori (Hallelujah Mountains), munți ce plutesc lent purtați de curenții magnetici asemănător aisbergurilor în mare, pe suprafața planetei formată din gaz lichid.

Pentru prospectarea și exploatarea zăcămintelor de minereu este necesară cartografierea suprafeței planetei și întocmirea unei hărți digitizate reprezentate sub forma unui tablou bidimensional. Astfel, regiunea de interes geologic este împărţită în N×N pătrate teritoriale identice (zone), fiecare zonă fiind identificată prin tripletul (x,y,c), unde (x,y) reprezintă coordonatele zonei teritoriale (x – linia, y – coloana), iar c cota (înălțimea). Între zonele ocupate de munții există vaste zone de gaz lichid, zone care au cota 0.

Pentru recoltarea și transportul unobtainiumului către baza stelară coloniștii RDA folosesc spice-harvesters, nave speciale cu aterizarea pe verticală.

Aterizarea pe munții plutitori reprezintă o adevărată provocare pentru piloții RDA. Pentru a putea ateriza, piloții trebuie să identifice un sector plat (platformă de aterizare), platformă care să respecte designul trenului de aterizare al navelor (vezi figura alăturată). Platforma are forma unui pătrat de latură k ce este format din k*k zone teritoriale, astfel (k*k)-4 zone au aceeași cotă, iar cele 4 colțuri ale pătratului au cota strict mai mică decât restul zonelor pătratului.

Cunoscând descrierea a M zone teritoriale ce alcătuiesc munții plutitori să se determine coordonatele colțului stânga-sus al platformelor de aterizare pentru munții plutitori care permit aterizarea.

Fie N și T două numere naturale.

Să se determine numărul soluțiilor diferite S, ale ecuației \( x_1 \cdot x_2 \cdot \cdots \cdot x_N = T \), în mulțimea numerelor naturale.

Scrieţi în limbajul C++ definiţia completă a subprogramului inmultire cu următorul antet:

void inmultire(matrice_rara a, matrice_rara b, matrice_rara &c)

ce calculează în c produsul matricelor rare a şi b.

Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

• substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

• medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.

Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte 1 m² şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând X m² de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni N x M, fiecare element al tabloului reprezentând exact 1 m². Pereţii sunt reprezentaţi prin caracterul ‘P’ iar suprafeţele camerelor prin caracterul ‘S’ (spaţiu). În planul din figura următoare este descrisă o locuinţă cu 5 camere acestea având respectiv, suprafeţele de 10, 2, 1, 3, 5 m².

PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.

Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Fiind date N, M, X şi planul locuinţei să se determine:

1. numărul C de camere pe care a reuşit să le acopere Gigel şi numărul R de m² de parchet care îi rămân, procedând aşa cum a hotărât iniţial;
2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet.

Să se verifice dacă un cuvânt dat este palindrom.

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?

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.

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.