| Fişierul intrare/ieşire: | paintball.in, paintball.out | Sursă | Lot Iasi 2008, Baraj 6 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paintball
După amiază la Iezăreni cei N membri ai lotului naţional de informatică vor participa la o partidă mai specială de paintball. Fiecare concurent va primi o armă şi o singură bilă cu vopsea.
În primul rând concurenţii sunt numerotaţi de la 1 la N. Având o singură bilă, fiecare concurent se gândeşte dinainte în cine va trage. Un concurent care a fost împuşcat cu o bilă de vopsea este declarat “mort” şi nu mai poate să tragă.
Concurenţii trag succesiv, în orice ordine doresc.
Cerinţă
Să se determine numărul minim şi numărul maxim de “morţi”.
Date de intrare
Fişierul de intrare paintball.in e prima linie numărul natural N reprezentând numărul de concurenţi. Pe cea de a două linie sunt scrise N numere naturale separate prin spaţii; al i-lea număr de pe linie reprezentând numărul concurentului în care va trage concurentul i.
Date de ieşire
Fişierul de ieşire paintball.out va conţine o singură linie pe care vor fi scrise două numere naturale separate prin spaţiu nrmin nrmax reprezentând numărul minim şi respectiv numărul maxim de “morţi”.
Restricţii
- 1 ≤ N ≤ 1.000.000
- Un concurent se poate împuşca pe sine însuşi.
Exemplu
| paintball.in | paintball.out |
|---|---|
| 8 2 3 2 2 6 7 8 5 | 3 5 |
Explicaţie
Dacă de exemplu ordinea în care trag concurenţii este 1, 4, 3, 5, 7 vor muri 2, 6, 8 (număr minim de morţi).
Dacă ordinea este: 2, 1, 4, 7, 6, 5 vor muri 3, 2, 8, 7, 6 (număr maxim de morţi).
