Fişierul intrare/ieşire:paintball.in, paintball.outSursăLot Iasi 2008, Baraj 6
AutorMircea Bogdan PasoiAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.9 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inpaintball.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content