turnuri

Time limit: 1s Memory limit: 16MB Input: turnuri.in Output: turnuri.outPoints by default: 10p

Într-un laborator cibernetic se fac experimente cu roboți. Pe o bandă de lucru se află așezate unul lângă altul, NN cuburi galbene și albastre, numeroate în ordine cu valori de la 11 la NN. Pentru fiecare cub se cunoaște latura acestuia, exprimată în centimetri, și culoarea, codificată prin simbolul gg (pentru galben) sau aa (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 KK peste cubul numerotat cu K1K-1 doar dacă el are culoarea diferită și latura mai mică decât cubul K1K-1. Această operație se efectuează în cazul în care cubul K1K-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 KK nu poate fi așezat peste cubul K1K-1, el rămâne la locul lui.

Cerință

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

  1. numărul final TT al turnurilor de pe bandă și HH, î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 NN 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 CC care reprezintă numărul cerinței și poate fi 11 sau 22.
  • pe cea de-a doua linie un număr natural NN ce reprezintă numărul cuburilor de pe bandă;
  • pe fiecare dintre următoarele NN linii, câte un număr natural care reprezintă latura unui cub, urmat de un spațiu și simbolul gg sau aa, pentru codificarea culorii cubului.

Date de ieșire

În fișierul de ieșire turnuri.out va conține pentru cerința 11 pe prima linie două valori, separate printr-un spațiu, ce reprezintă TT și HH. Pentru cerința 22 fișierul va conține pe prima linie numărul NmaxNmax.

Restricții și precizări

  • 1N10 0001 \leq N \leq 10 \ 000 și 11 \leq latura unui cub 500 000\leq 500 \ 000;
  • nu există două cuburi cu laturi egale;
  • se acordă 1010 puncte din oficiu. Pentru rezolvarea corectă a primei cerințe se acordă 3030 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 6060 de puncte.

Exemplul 1

turnuri.in

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

turnuri.out

3 31

Explicație

Se va rezolva cerința 11. Al doilea cub se așază peste primul și formează un turn cu înălțimea de 3131 de centimetri. Al treilea cub formează singur un turn cu înălțimea 1515 centimetri. Ultimele trei cuburi formează un turn cu înălțimea 2020 de centimetri. Numărul turnurilor este 33. Înălțimea celui mai înalt turn este de 3131 de centimetri.

Exemplul 2

turnuri.in

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

turnuri.out

5

Explicație

Se va rezolva cerința 22. O posibilă rearanjare a cuburilor ar fi următoarea:

Primele 55 cuburi formează un turn.

Log in or sign up to be able to send submissions!