2445 - Turnuri 1

Într-un laborator cibernetic se fac experimente cu roboţi. Pe o bandă de lucru se află aşezate unul lângă altul, N cuburi galbene şi albastre, numeroate în ordine cu valori de la 1 la N. Pentru fiecare cub se cunoaşte latura acestuia, exprimată în centimetri, şi culoarea, codificată prin simbolul g (pentru galben) sau a (pentru albastru). Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. El se află în faţa benzii de lucru, analizează fiecare cub în ordine, de la primul la ultimul, şi procedează astfel :

• dacă este primul cub, îl lasă la locul lui pe bandă;
• aşează cubul numerotat cu K peste cubul numerotat cu K-1 doar dacă el are culoarea diferită şi latura 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 constuit anterior sau dacă el a rămas în poziția inițială. În cazul în care cubul K nu poate fi aşezat peste cubul K-1, el rămâne la locul lui.

Cerința

Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine:

1. numărul final T al turnurilor de pe bandă şi H, înălţimea celui mai înalt turn care se poate forma, exprimată în centimetri;

2. cel mai mare număr de cuburi Nmax ce pot forma un turn, dacă cele N cuburi ar putea fi rearanjate inițial pe bandă, unul lângă altul.

Date de intrare

Fişierul turnuri1.in conţine:

- pe prima linie un număr natural C care reprezintă numărul cerinţei şi poate fi 1 sau 2.

- pe cea de-a doua linie un număr natural N ce reprezintă numărul cuburilor de pe bandă;

- pe fiecare dintre următoarele N linii, câte un număr natural care reprezintă latura unui cub, urmat de un spaţiu şi simbolul g sau a, pentru codificarea culorii cubului.

Date de ieșire

Fișierul de ieșire turnuri1.out va conţine pentru cerința 1 (C=1) pe prima linie două valori, separate printr-un spațiu, ce reprezintă T și H. Pentru cerința 2 (C=2) fișierul va conține pe prima linie numărul Nmax.

Restricții și precizări

• 1 ≤ N ≤ 10 000 şi 1≤ latura unui cub ≤ 500 000;
• nu există două cuburi cu laturi egale;
• Pentru rezolvarea corectă a primei cerințe se acordă 30 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.
• În concurs s-au acordat 10 din oficiu. Aici se acordă 10 puncte pentru exemplele din enunț.

Exemplul 1:

turnuri1.in

1
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri1.out

3 31

Încărcare soluție

Lipește codul aici

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

1. Framework and technology stack: C++ with standard library

import sys from typing import List

fin = open("turnuri1.in", "r") fout = open("turnuri1.out", "w") C: int n: int n1: int n2: int nr_turnuri: int max_turn: int v1: List[int] = [0] * 10003 v2: List[int] = [0] * 10003 v3: int

def citire() -> None:

   global C, n, n1, n2, nr_turnuri, max_turn
   l1: int
   l2: int
   h_turn: int
   cul1: str
   cul2: str

   data = fin.readline().split()
   C = int(data[0])
   n = int(data[1])

   data = fin.readline().split()
   l1 = int(data[0])
   cul1 = data[1]
   nr_turnuri = 1
   h_turn = l1
   if cul1 == 'g':
       n1 += 1
       v1[n1] = l1
   else:
       n2 += 1
       v2[n2] = l1

   for i in range(n - 1):
       data = fin.readline().split()
       l2 = int(data[0])
       cul2 = data[1]

       if l2 < l1 and cul2 != cul1:
           h_turn += l2
       else:
           nr_turnuri += 1
           h_turn = l2
       if h_turn > max_turn:
           max_turn = h_turn
       l1 = l2
       cul1 = cul2

def cmp(a: int, b: int) -> bool:

   return a > b

def main() -> None:

   global n1, n2, v1, v2
   i: int
   j: int
   k: int
   p: int
   citire()
   if C == 1:
       fout.write(str(nr_turnuri) + ' ' + str(max_turn) + '\n')
   else:
       v1 = sorted(v1[1:n1 + 1], reverse=True)
       v2 = sorted(v2[1:n2 + 1], reverse=True)
       v1.append(500003)
       v2.append(500002)
       i = 1
       j = 1
       k = 0
       if v1[i] > v2[j]:
           k += 1
           v3 = v1[i]
           i += 1
           p = 1
       else:
           k += 1
           v3 = v2[j]
           j += 1
           p = -1
       while i <= n1 and j <= n2:
           if p == 1:
               while j <= n2 and v2[j] >= v3:
                   j += 1
               if j <= n2:
                   k += 1
                   v3 = v2[j]
                   j += 1
                   p = -p
           else:
               while i <= n1 and v1[i] >= v3:
                   i += 1
               if i <= n1:
                   k += 1
                   v3 = v1[i]
                   i += 1
                   p = -p
       if p == -1:
           for i in range(i, n1 + 1):
               if v1[i] < v3:
                   k += 1
                   v3 = v1[i]
                   break
       if p == 1:
           for j in range(j, n2 + 1):
               if v2[j] < v3:
                   k += 1
                   v3 = v2[j]
                   break
       fout.write(str(k) + '\n')

   fin.close()
   fout.close()

if __name__ == "__main__":

   main()

</syntaxhighlight>