Lista de probleme 733

Alex și Mircea, membri veterani ai Comisiei de Entertainment la concursurile de informatică, au fost chemați de către comisia științifică să participe la ediția de anul acesta a concursului InfoOltenia. Comisia științifică le-a spus acestora locația secretă în care se află și le-a transmis că îi așteaptă cu nerăbdare. Cum Alex și Mircea nu pot spune pas la o asemenea ocazie, se pregătesc imediat de plecare. Aceștia, fiind pasionați și de informatică în timpul liber, își pun următoarea întrebare: în câte moduri pot ajunge de la ei de acasă până la locația comisiei științifice?

Formal, harta județului Vâlcea poate fi interpretată ca un grid, în care veteranii se află la coordonatele (0,0), iar comisia se află la coordonatele (m,n). Cum veteranii nu se deplasează decât înainte, dintr-o celulă de coordonate (i,j), aceștia pot face următorul pas într-una din celulele aflate la coordonate (i+1,j), (i,j+1) sau (i+1,j+1). Să se calculeze numărul de moduri în care Alex și Mircea pot ajunge la locația comisiei științifice. Cum numărul acesta poate fi foarte mare, se vrea furnizată valoarea acestuia modulo 666013.

În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înânlțimea copacului i. Apoi i-au venit în minte două întrebări.

Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.

A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).

În clasa lui Dexter sunt N elevi de înălțimi distincte. La ora de sport, ei sunt așezați în linie, de la stânga la dreapta. Profesorul lor, Johnny, va selecta pentru un exercițiu elevi aflați pe poziții consecutive în linie, astfel încât cel mai înalt elev dintre cei selectați să se afle în prima jumătate a acestora.

De exemplu, dacă elevii au, în ordine, înălțimile 1, 5, 4, atunci profesorul poate să îi selecteze pe cei cu înălțimile 5 și 4, dar nu poate să îi selecteze pe cei cu înălțimile 1 și 5. Desigur, există mai multe moduri de a selecta elevii astfel încât să fie satisfăcută condiția de mai sus. Profesorul Johnny ar vrea să afle în câte moduri se poate face acest lucru.

Dându-se N și înălțimile elevilor din clasă, aflați în câte moduri pot fi selectați oricâți elevi aflați pe poziții consecutive, astfel încât să fie îndeplinită condiția din enunț.

Dexter și-a definit propriul algoritm de arhivare a șirului favorit T, șir format numai din litere mici ale alfabetului englez. Șirul arhivat, notat cu S, poate fi format din cifre, litere mici ale alfabetului englez, parantezele drepte '[' și ']' și parantezele rotunde '(' și ')', precum și caractere '*'.

Fixi, curios din fire, descoperă algoritmul și încearcă să dezarhiveze șirul S, prin efectuarea unor transformări repetate. O transformare poate fi de unul dintre cele 3 tipuri de mai jos, unde s-a notat cu C o secvență din S formată numai din litere.

1. O secvență a lui S de forma n(C), unde n este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvență D obținută prin scrierea concatenată, de n ori, a șirului C. Exemplu: pentru secvența 10(ab) avem n=10 și se obține secvența D=abababababababababab.
2. O secvență a lui S de forma [*C] se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvenței C cu oglinditul lui C. Exemplu: din secvența [*abc] se obține secvența palindromică de lungime pară abccba
3. O secvență a lui S de forma [C*] se transformă într-o secvență palindromică de lungime impară, obținută prin concatenarea secvenței C cu oglinditul lui C din care s-a eliminat primul caracter. Exemplu: din secvența [abc*] se obține secvența palindromică de lungime impară abcba.

Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

Fiind dat șirul arhivat S să se determine numărul de transformări, de cele 3 tipuri de mai sus, realizate de Fixi în cadrul algoritmului de dezarhivare, precum și forma finală dezarhivată T a șirului S.

Se consideră modelul unui sistem solar format din N planete care se rotesc în jurul unei stele S, în sens trigonometric. Traiectoriile planetelor se consideră circulare și de raze diferite, iar vitezele de rotație ale planetelor în jurul stelei sunt numere naturale și sunt exprimate în grade pe zi (⁰/zi).

Cunoscând numărul de planete N și vitezele lor de rotație Vi, 1≤i≤N precum și două numere naturale P și Z, să se determine numărul A de alinieri a câte minimum P planete, pe o dreaptă ce trece prin centrul stelei S, după trecerea celor Z zile. Evoluția sistemului solar începe cu toate planetele așezate orizontal, în dreapta stelei S.

Într-o țară îndepărtată, economia este în criză. Cea mai mare problemă este lipsa de capital care creează blocaje financiare. De exemplu, o firmă X poate avea datorii către o firmă Y pe care nu le poate plăti, deoarece o altă firmă Z are datorii către firma X pe care nu le-a plătit, ş.a.m.d.

Există o listă cu toate datoriile firmelor sub forma următoare:

X > Y S

cu semnificaţia “firma X datorează firmei Y suma S”. Este posibil ca X să aibă mai multe datorii la firma Y (în funcţie de contractele derulate împreună) sau chiar ca X să aibă datorii la Y și Y să aibă datorii la X.

Cunoscând lista cu datoriile firmelor, scrieți un program care să rezolve următoarele cerințe:

1. determină numărul de firme distincte care apar în această listă;
2. realizează o situație financiară a firmelor distincte din această listă, scrise în ordine lexicografică; pentru fiecare firmă se vor determina două valori SD SP, unde SD reprezintă suma totală a datoriilor pe care firma le are către alte firme, iar SP este totalul sumelor pe care firma trebuie să le primească de la alte firme.

Fie o matrice (care are M linii si N coloane) colorată folosind C culori. Aceasta este K-frumoasă doar dacă are exact K coloane omogene. O coloană omogenă este o coloană care are toate elementele colorate la fel.

Redefiniți instruțiunea condițională if, printr-o secvență de directive #define.

Un cuvânt se numește k-ps dacă prefixul său de lungime k este identic cu sufixul de lungime k, iar k este cea mai mare valoare strict mai mică decât lungimea cuvântului, cu această proprietate. Dacă nu există nicio astfel de valoare k nenulă, spunem despre cuvânt că este 0-ps. De exemplu, amalgam este 2-ps, iar amestec este 0-ps.

Rezolvați următoarele cerințe:

1) Se dă un cuvânt. Determinați k asfel încât cuvântul să fie k-ps.
2) Se dă un șir de caractere în care cuvintele sunt alcătuite din litere mici ale alfabetului englez și sunt separate prin spații. Să se afișeze în ordine cuvintele 0-ps, 1-ps, 2-ps, 3-ps, etc, până la cel mai mare k pentru care există în șir cel puțin un cuvânt k-ps. Pentru fiecare categorie, cuvintele vor fi afișate în ordine alfabetică.

Se consideră un castel de formă dreptunghiulară, alcătuit din n*m camere dispuse pe n linii și m coloane. Intrarea în castel este în camera de coordonate (1,1), ieșirea în camera de coordonate n,m, unele camere sunt închise, dintr-o cameră se poate trece în camerele învecinate pe linie și pe coloană, iar unele camere sunt ocupate de zmei gripați, fiecare zmeu afectând camera sa și camere aflate în jurul său la distanța mai mică sau egală cu k.

Pentru a câștiga inima Ilenei Cosânzeana, Făt-Frumos trebuie să traverseze castelul. Deoarece nu se pricepe la informatică vă roagă pe voi să determinați care este lungimea minimă a unui traseu care traversează castelul, trece doar prin camere deschise și nu trece prin camere afectate de zmei.