În acest an evenimentul ”Hour of Code” a înregistrat un număr record de participanţi din ţara noastră. În cadrul acestui eveniment una dintre cele mai accesate aplicaţii a fost Lightbot, care a permis elevilor să-şi testeze abilităţile de programare.
Aplicaţia Lightbot are N nivele, numerotate consecutiv de la 1 la N, în ordinea strict crescătoare a complexităţii lor. Lightbot a permis fiecărui participant să înceapă cu orice nivel strict mai mic decât N-1 şi să sară peste un singur nivel, fără a finaliza codul, trecând la nivelul următor celui sărit. La finalizarea cu succes a codului corespunzător nivelului curent, participantul este promovat la nivelul imediat următor. Fiecare participant a început scrierea codurilor la un nivel P şi a sărit peste un nivel L (P < L < P + K), finalizând K nivele memorate ca o succesiune de numere naturale de forma P, P+1,..., L-1, L+1,..., P+K. Succesiunile de nivele finalizate de participanţi au fost memorate în fişierul lightbot.in. Succesiunile corespunzătoare participanţilor nu se intercalează în fişier.
Cerinţă
Scrieţi un program care citeşte succesiunile corespunzătoare nivelelor finalizate de participanţii care au jucat Lightbot şi determină:
1. numărul total de participanţi;
2. numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi;
3. pentru fiecare participant, numărul nivelului sărit de acesta.
Date de intrare
Fişierul de intrare lightbot.in conţine pe prima linie una dintre valorile 1 , 2 sau 3, reprezentând cerinţa 1 dacă se cere determinarea numărului total de participanţi, cerinţa 2 dacă se cere determinarea numărului celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi, respectiv cerinţa 3, dacă se cere determinarea, pentru fiecare participant, a numărului nivelului sărit de acesta.
A doua linie a fişierului conţine numărul natural N de nivele corespunzător aplicaţiei Lightbot, iar pe a treia linie, succesiunile de numere naturale nenule corespunzătoare nivelelor finalizate de participanţi, separate două câte două prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire lightbot.out va conţine pe prima linie un număr natural M, reprezentând numărul total de participanţi dacă cerinţa a fost 1, un număr natural reprezentând numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi, dacă cerinţa a fost 2, respectiv, o secvenţă de M numere naturale separate prin câte un spaţiu ce reprezintă nivele sărite de participanţi în ordinea succesiunilor memorate în fişier, dacă cerinţa a fost 3.
Restricţii
• 3 ≤ N ≤ 200000.
• 1 ≤ X ≤ N, pentru orice număr X memorat pe a treia linie a fişierului lightbot.in.
• 1 ≤ P < L < P + K ≤ N, pentru orice succesiune de K nivele finalizate, corespunzătoare unui participant, care a început scrierea codurilor la nivelul P şi a sărit peste nivelul L.
• O secvenţă de valori consecutive aparţine unui singur participant.
• A treia linie a fişierului de intrare conţine cel mult 400000 de numere.
• Pentru rezolvarea corectă a cerinţei 1 se obţine 20% din punctaj.
• Pentru rezolvarea corectă a cerinţei 2 se obţine 40% din punctaj.
• Pentru rezolvarea corectă a cerinţei 3 se obţine 40% din punctaj.
Exemple
lightbot.in
lightbot.out
Explicaţii
1
10
1 2 4 2 4 6 7 9
3
Sunt trei participanţi, care au finalizat nivelele: 1 2 4 (primul), 2 4 (al doilea) şi 6 7 9 (al treilea).
2
10
1 2 4 2 4 6 7 9
4
Nivele 2 şi 4 au fost finalizate de câte doi participanţi, cel mai greu fiind nivelul 4.
3
10
1 2 4 2 4 6 7 9
3 3 8
Primul participant a sărit nivelul 3, al doilea nivelul 3, iar al treilea nivelul 8.