Lista de probleme 854

Cea mai cunoscută măsură a unui vârf de munte este altitudinea sa. Vârfuri secundare ale unui munte înalt pot avea altitudini considerabile, dar în general acestea nu sunt atât de relevante. Din acest motiv, geografii au introdus o nouă măsură pentru un vârf: proeminenţa. Un profil este o reprezentare a altitudinilor în puncte succesive, între care ne putem deplasa la stânga sau dreapta. Scrieţi un program care, cunoscând configuraţia unui profil, rezolvă următoarele două cerinţe:
1) determină numărul de vârfuri existente pe profilul respectiv;
2) determină proeminenţa fiecărui vârf de pe profil.

Alexandra citește un text format din litere mici și mari ale alfabetului englez și spații. Fiind interesată de criptografie, ea elimină toate spațiile și apoi încadrează literele, în ordinea în care acestea apar în text, într-un tablou bidimensional, în care numărul de linii este mai mic sau egal decât numărul de coloane. Întrucât pot exista mai multe moduri de încadrare a textului, Alexandra îl alege pe cel pentru care diferența absolută dintre numărul liniilor și al coloanelor tabloului este minimă.
1) Notând cu N numărul de linii și cu M numărul de coloane ale tabloul bidimensional obținut, afișați elementele acestuia pe primele N linii ale fișierului de ieșire, fiecare linie conținând exact M litere fără spații între ele. Afișarea se va face în ordinea crescătoare a indicilor liniilor și pe fiecare linie în ordinea crescătoare a indicilor coloanelor.
2) Determinați cel mai lung palindrom de pe o linie sau de pe o coloană a tabloului obținut. În cazul în care există mai multe palindroame de aceeași lungime, se va afișa cel care este cel mai mare din punct de vedere lexicografic conform codului ASCII.
3) Determinați care este numărul maxim de elemente dintr-un subtablou dreptunghiular, ce conține doar vocale.

Dat fiind un șir de N numere naturale A[1], A[2], …, A[N], și un algoritm, prezentat în pseudocod, care este valoarea lui cnt la sfârșitul algoritmului? Care este valoarea lui score la sfârșitul algoritmului, modulo 666.013?

Anul 1905. Un stat din America de Sud și-a propus investiții majore în infrastructura feroviară. Brazilianul Badinho este managerul unei companii de transport feroviar pe o magistrală importantă. De-a lungul magistralei se află N stații, numerotate de la 1 la N. Fiecărei stații îi corespunde un număr Xi care reprezintă numărul de kilometri de la începutul magistralei până la stația i (X1 = 0). Știind că Badinho trebuie să cheltuiască întreaga sumă pe care ar primi-o dintr-o subvenție, să se determine:
-Numărul de moduri de a deschide o rută de tip Regio, modulo 1.000.000.007
-Numărul de moduri de a deschide o rută de tip Expres, modulo 1.000.000.007

Data stelară 3210: Căpitanul navei USS Entrerprise, Jean-Luc Picard se află într-o misiune importantă în cuadrantul Beta al galaxiei. Acesta trebuie să ajungă cât mai rapid de la planeta Vulcan până la planeta Qo’noS, dar din păcate pentru această misiune Jean-Luc Picard nu va putea să ajungă instantaneu la destinație folosind warp drive-ul navei, ci va trebui să se deplaseze în mod normal, din sector în sector. Vouă vă revine rolul de a îl ajuta pe Jean-Luc Picard și să îi răspundeți la una din următoarele întrebări știind harta galaxiei:
- Care este numărul maxim de sectoare ale galaxiei Smax afectate la orice moment de timp de către cel puțin un pulsar.
- Care este timpul minim Tmin de care are nevoie Jean-Luc Picard pentru a ajunge pe planeta Qo’noS.

O imprimantă circulară are litere mari ale alfabetului englezesc dispuse circular de la A la Z. Imprimanta are un indicator care inițial este plasat la litera A. Imprimanta tipărește literele în două culori roșu sau albastru. Unele litere se tipăresc cu cerneală roșie, restul cu cerneală albastră. Pentru simplitate le vom numi litere roșii și litere albastre. Fiind date un șir de litere albastre nu neapărat distincte și mulțimea literelor roșii ale imprimantei, să se calculeze:

• Care este timpul pentru tipărirea la imprimantă circulară a șirului de litere albastre.
• Să se insereze între oricare două litere albastre aflate pe poziții consecutive câte o literă roșie astfel încât să se obțină timpul minim pentru tipărire și să se afișeze: timpul minim, numărul de șiruri distincte care sunt tipărite cu timp minim, șirul minim lexicografic dintre toate șirurile ce sunt tipărite în acest timp

La ferma din comuna Iepurești există un teren de forma dreptunghiulară în care fermierii satului au creat mai multe grădini în care au plantat morcovi. Terenul este împărțit în nxm unități. Morcovii nu sunt plantați uniform astfel încât în celule diferite pot exista numere diferite de morcovi. Iepurele Ronți vrea să știe în ce gradină să intre pentru a aduna cât mai mulți morcovi dintr-un singur raid asupra terenului.

Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup. Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvamontiști. Informaticienii reușesc să analizeze spațiile sigure ale versantului. Ei vă cer ajutorul pentru a reuși să-i salveze pe alpiniști.

Te afli într-o cameră de formă dreptunghiulară, privită sub forma unei matrici cu N linii și M coloane. Camera depozitează alune, nuci și castane, fiecare celulă din matrice fiind însemnată cu un caracter din mulțimea {'A', 'N', 'C'}. O celulă care conține caracterul 'A' reprezintă o alună, una care conține caracterul 'N' marchează o nucă, iar una care conține caracterul 'C' codifică o castană. Cum castanele depozitate nu sunt comestibilie, tu ai dori să vezi câte submatrici cu laturile paralele cu cele ale camerei inițiale poți alege, astfel încât numărul de alune să fie egal cu numărul de nuci.

Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită.