0877 - Cuburi2

Cerința

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 latura mai mică sau egală cu cubul din vârful stivei, 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.

Date de intrare

Programul citește de la tastatură numărul n, apoi n numere naturale, reprezentând, în ordine, lungimile laturilor cuburilor.

Date de ieșire

Programul va afișa pe ecran numărul de cuburi existente pe stivă, iar pe linia următoare, separate prin câte un spațiu, numerele marcate pe aceste cuburi.

Restricții și precizări

• 1 ≤ n ≤ 1000
• lungimile cuburilor vor fi mai mici decât 1000

Exemplul 1:

Intrare

6

7 4 3 5 1 2

Ieșire

Datele de intrare corespund restrictiilor impuse.

3

1 4 6

Exemplul 2:

Intrare

x

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def verificare_restrictii(nr_n): # functia de verificare a datelor de intrare

   if 1 <= nr_n <= 1000:
       return True
   else:
       return False

def procesare_cuburi(nr_n, cuburi):

   # Initializam stiva si lista de numere
   stack = []
   numbers = []

   # Parcurgem fiecare cub
   for i in range(nr_n):
       # Cat timp stiva nu este goala si cubul curent are latura mai mare decat cubul din varful stivei
       while stack and stack[-1] < cuburi[i]:
           # Eliminam cubul din varful stivei
           stack.pop()
           # Eliminam numarul corespunzator cubului eliminat
           numbers.pop()
       # Adaugam cubul curent in stiva
       stack.append(cubes[i])
       # Adaugam numarul corespunzator cubului curent in lista de numere
       numbers.append(i + 1)

   # Afisam numarul de cuburi ramase in stiva
   print(len(numbers))
   # Afisam numerele corespunzatoare cuburilor ramase in stiva
   print(' '.join(map(str, numbers)))

if __name__ == '__main__':

   try:
       n = int(input("Introduceti numarul de cuburi: "))     # citirea numarului de cuburi
       cubes = list(map(int, input().split()))               # citirea lungimilor laturilor cuburilor

       if verificare_restrictii(n):                          # verificam datele de intrare
           print("Datele de intrare corespund restrictiilor impuse.")
           procesare_cuburi(n, cubes)                        # apelam functia de rezolvare
       else:
           print("Datele de intrare nu corespund restrictiilor impuse.")
   # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicație

Operațiile efectuate sunt:

• se adaugă cubul 1. Stiva devine 1
• se adaugă cubul 2. Stiva devine 1 2
• se adaugă cubul 3. Stiva devine 1 2 3
• pentru a adaugă cubul 4, trebuie eliminate cuburile 2 3. Stiva devine 1 4
• se adaugă cubul 5. Stiva devine 1 4 5
• pentru a adaugă cubul 6, trebuie eliminat cubul 5. Stiva devine 1 4 6