Lista de probleme

#687 liste

Numim listă un sir de numere naturale. Avem la dispoziţie mai multe liste aşezate, în ordine, una sub alta. Spunem că două liste L1 şi L2 sunt vecine dacă L1 este imediat deasupra lui L2, sau dacă L2 este imediat deasupra lui L1. Oricare două liste vecine L1 şi L2 pot fi unificate dacă ele au cel puţin un element comun. Prin unificare, noua listă va avea ca elemente toate elementele din L1 la care se adaugă toate elementele din L2. Listele L1 şi L2 vor dispărea şi în locul lor va apărea noua listă.

Determinaţi numărul minim de liste care rezultă după aplicarea unui număr suficient de unificări astfel încât să nu mai existe două liste vecine care să poată fi unificate.

Lot Juniori, Sibiu 2011

Gigel are un set de n cuburi. Fiecare cub este marcat cu un număr natural, de la 1 la n și i se cunoaște lungimea laturii – număr natural. Cu o parte dintre aceste cuburi Gigel va construi o stivă, astfel:

  • fiecare cub se analizează o singură dată, în ordinea numerelor marcate;
  • dacă stiva nu conține niciun cub, cubul curent devine baza stivei
  • dacă cubul curent are mai latura mai mică sau egală cu cubul din vârful stive, se adaugă pe stivă;
  • dacă cubul curent are latura mai mare decât cubul din vârful stivei, se vor înlătura de pe stivă cuburi (eventual toate) până când cubul curent are latura mai mică sau egală cu cubul din vârful stivei.

Să se afișeze numerele de pe cuburile existente la final în stivă, de la bază spre vârf.

#875 Stiva

Să se scrie un program care gestionează o stivă de numere întregi. Inițial stiva este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:

  • push X – adaugă valoarea întreagă X pe stivă;
  • pop – elimină elementul din vârful stivei;
  • top – afișează elementul din vârful stivei.

Programul va realiza asupra stivei operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.

Se consideră un șir de n intervale închise întregi. Două intervale consecutive în șir care au intersecția nevidă se reunesc și se înlocuiesc în șir cu intervalul reuniune. Operația se repetă până când nu mai sunt în șir două intervale consecutive cu intersecția nevidă.

Să se determine câte intervale există în șir după realizarea acestor operații.

#870 Depou

Se consideră un depou de cale ferată precum cel din imagine:

Pe linia A se află n vagoane, numerotate cu valori distincte de la 1 la n, într-o ordine oarecare. Vagoanele trebuie mutate pe linia C, în ordinea 1 2 .. n. Pentru aceasta se poate muta câte un vagon de pe o linie pe alta, în ordinea indicată de săgeți:
A -> B, A -> C sau B -> C.

Să se determine o succesiune de operații care să mute toate vagoanele de pe linia A pe linia C în ordinea dorită.

Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat.

Se dau n șiruri de paranteze rotunde sau pătrate. Să se stabilească, despre fiecare șir, dacă este corect parantezat.

Se dă un șir de paranteze rotunde care se închid corect (corect parantezat). Să se determine adâncimea parantezării.

#1884 UEMM1

Se dă un șir cu n elemente, numere naturale. Să se afișeze, pentru fiecare element din șir, valoarea din șir aflată după acesta și mai mare decât acesta. Dacă o asemenea valoare nu există, se va afișa -1.

#874 Atomi

Într-o galaxie îndepărtată există doar două elemente chimice. Cercetătorii le-au numit A şi B şi toate substanţele sunt alcătuite din aceste elemente. Mai precis, o substanţă este un şir definit astfel:

  • A şi B sunt substanţe, formate din câte un atom;
  • Ax şi By sunt substanţe, x şi y find numere naturale. Ax este formată din x atomi de tip A, iar By este formată din y atomi de tip B;
  • dacă S este substanţă atunci (S)x este substanţă, x fiind un număr natural. Dacă în S sunt p atomi, în (S)x vor fin p*x atomi;
  • dacă S şi T sunt substanţe atunci ST este substanţă. Dacă în S sunt x atomi, iar în T sunt y atomi, în ST vor fi x+y atomi.

Pentru o substanţă dată să se determine numărul atomilor de tip A şi numărul atomilor de tip B care o compun.