Fișierul intrare/ieșire	turnuri.in, turnuri.out	Sursă	OJI 2018 clasa a 6-a
Autor	Cristina Iordaiche	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Turnuri (clasa a 6-a)

Î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șază 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 construit 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țe

Ș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 de intrare turnuri.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

În fișierul de ieșire turnuri.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

• 1≤ N ≤ 10 000 și 1 ≤ latura unui cub ≤ 500 000;
• nu există două cuburi cu laturi egale;
• se acordă 10 puncte din oficiu. 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.

Exemplu

turnuri.in	turnuri.out	Explicație
1 6 18 a 13 g 15 a 10 a 8 g 2 a	3 31	Se va rezolva cerința 1. Al doilea cub se așază peste primul și formează un turn cu înălțimea de 31 de centimetri. Al treilea cub formează singur un turn cu înălțimea 15 centimetri. Ultimele trei cuburi formează un turn cu înălțimea 20 de centimetri. Numărul turnurilor este 3. Înălțimea celui mai înalt turn este de 31 de centimetri.
2 6 18 a 13 g 15 a 10 a 8 g 2 a	5	Se va rezolva cerința 2. O posibilă rearanjare a cuburilor ar fi următoarea:   Primele 5 cuburi formează un turn.