3645 - Cuburi 4

Sursa: [1]

Cerinţa

Pe o masă, sunt așezate unul lângă altul, N cuburi numerotate în ordine cu valori de la 1 la N, care au dimensiunea laturii exprimată în centimetri, printr-un număr natural nenul. Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. El se află în faţa mesei de lucru, analizează în ordine fiecare cub, de la primul la ultimul, şi procedează astfel:

dacă este la primul cub, îl lasă la locul lui pe masă; aşează cubul numerotat cu K peste cubul numerotat cu K-1 doar dacă el are latura strict mai mică decât cubul K-1. Această operaţie se efectuează în cazul în care cubul K-1 se află deja într-un turn construit anterior sau dacă el a rămas pe masă. În cazul în care cubul K nu poate fi aşezat peste cubul K-1, el rămâne la locul lui pe masă.

Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine: 1. cel mai mare număr de cuburi alăturate care au laturile exprimate printr-un număr par de centimetri; 2. înălţimea (exprimată în centimetri) celui mai înalt turn construit de robot.

Date de intrare

De la tastatură se citesc două numere natural C și N, în această ordine. C reprezintă numărul cerinţei şi poate avea două valori 1 sau 2 iar N reprezintă numărul cuburilor de pe masa de lucru. Se citesc apoi N numere naturale ce reprezintă lungimile laturilor cuburilor, în ordinea numerotării acestora.

Date de ieșire

Pe ecran se va afișa un singur număr natural corespunzător rezultatului obținut pentru rezolvarea fiecărei cerințe.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează cerintele de mai sus.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

1 ≤ N ≤ 10.000 și 1 ≤ latura unui cub ≤ 500.000;

există cel puțin un cub care are latura exprimată printr-un număr par de centimetri;

pentru rezolvarea corectă a primei cerințe se acordă 30 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 70 de puncte.

Exemplul 1

Datele de intrare

C este:

1

N este:

7

Lungimile laturilor sunt:

18

Lungimile laturilor sunt:

12

Lungimile laturilor sunt:

10

Lungimile laturilor sunt:

17

Lungimile laturilor sunt:

8

Lungimile laturilor sunt:

2

Lungimile laturilor sunt:

7

Datele sunt introduse corect.

Datele de ieșire

3

Exemplul 2

Datele de intrare

C este:

2

N este:

7

Lungimile laturilor sunt:

18

Lungimile laturilor sunt:

12

Lungimile laturilor sunt:

10

Lungimile laturilor sunt:

17

Lungimile laturilor sunt:

8

Lungimile laturilor sunt:

2

Lungimile laturilor sunt:

7

Datele sunt introduse corect.

Datele de ieșire

40

Rezolvare

<syntaxhighlight lang="python" line>

1. 3645

def max_even_sequence(laturi):

   # Cerința 1: lungimea maximă a unei secvențe de cuburi cu laturi exprimate printr-un număr par de centimetri
   max_par = 0
   last_par = -1
   count = 0
   for i in range(len(laturi)):
       if laturi[i] % 2 == 0:
           if i - last_par > 1:
               count = 0
           count += 1
           last_par = i
           max_par = max(max_par, count)
   return max_par

def max_tower_height(laturi):

   # Cerința 2: înălțimea maximă a unui turn
   height = [0]  # înălțimea maximă a turnului la fiecare pas
   stack = [laturi[0]]  # cuburile din turnul curent
   for i in range(1, len(laturi)):
       if laturi[i] < laturi[i-1]:
           stack.append(laturi[i])
       else:
           # adăugăm cuburile din stivă la turnul anterior
           while len(stack) > 1 and stack[-1] >= stack[-2]:
               stack.pop()
           height.append(sum(stack))
           stack = [laturi[i]]
   # adăugăm înălțimea ultimului turn
   while len(stack) > 1 and stack[-1] >= stack[-2]:
       stack.pop()
   height.append(sum(stack))
   return max(height)

if __name__ == '__main__':

   c = int(input("C este:"))
   n = int(input("N este:"))
   if not 1 <= n <= 500:
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   laturi = []
   for i in range(n):
       lat = int(input("Lungimile laturilor sunt: "))
       if not 1 <= lat <= 10000:
           print("Datele nu corespund restricțiilor impuse.")
           exit()
       laturi.append(lat)

   if c == 1:
       print("Datele sunt introduse corect.")
       print(max_even_sequence(laturi))
   else:
       print("Datele sunt introduse corect.")
       print(max_tower_height(laturi))

</syntaxhighlight>

Explicatie cod:

Această bucată de cod conține două funcții care rezolvă cele două cerințe ale problemei și un bloc de cod care primește datele de intrare, verifică dacă sunt valide și apelează funcția corespunzătoare.

Prima funcție, max_even_sequence(laturi), determină lungimea maximă a unei secvențe de cuburi cu laturi exprimate printr-un număr par de centimetri. Acest lucru se face prin parcurgerea listei de laturi și numărarea consecutivă a cuburilor cu laturi pare. Dacă apare un cub cu laturi impare sau o pauză între două cuburi pare este mai mare de 1, se resetează numărul de cuburi pare consecutive. Funcția returnează lungimea maximă a unei astfel de secvențe.

A doua funcție, max_tower_height(laturi), determină înălțimea maximă a unui turn. Algoritmul începe prin adăugarea primului cub la o stivă și inițializarea înălțimii turnului curent la 0. Apoi, pentru fiecare cub următor, acesta este comparat cu cubul anterior. Dacă cubul curent este mai mic decât cel anterior, atunci este adăugat la stiva turnului curent. Dacă cubul curent este mai mare sau egal cu cel anterior, atunci toate cuburile din stiva turnului curent sunt adăugate la înălțimea turnului anterior și o nouă stivă este începută cu cubul curent. Acest proces se repetă pentru fiecare cub din lista de laturi. În final, se calculează înălțimea ultimului turn și se determină înălțimea maximă dintre toate turnurile. Funcția returnează înălțimea maximă a turnului.

Blocul de cod care primește datele de intrare verifică mai întâi dacă numărul de laturi este în intervalul 1-500 și dacă fiecare latură este între 1 și 10000. Dacă aceste condiții nu sunt îndeplinite, programul se oprește și afișează un mesaj corespunzător. Dacă datele de intrare sunt valide, programul apelează funcția corespunzătoare pentru a rezolva problema și afișează rezultatul.