1217 - LightBot

Î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 input.txt. Succesiunile corespunzătoare participanților nu se intercalează în fișier.

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 input.txt 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 output.txt 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 și precizări

• 3 ≤ N ≤ 200000.

Exemplul 1

input.txt:

1

10

1 2 4 2 4 6 7 9

output.txt:

3

Explicație:

Sunt trei participanți, care au finalizat nivelele: 1 2 4 (primul), 2 4 (al doilea) şi 6 7 9 (al treilea).

Exemplul 2

input.txt:

2

10

1 2 4 2 4 6 7 9

output.txt:

4

Explicație:

Nivele 2 și 4 au fost finalizate de câte doi participanți, cel mai greu fiind nivelul 4.

Exemplul 3

input.txt:

3

10

1 2 4 2 4 6 7 9

output.txt:

3 3 8

Explicație:

Primul participant a sărit nivelul 3, al doilea nivelul 3, iar al treilea nivelul 8.

Exemplul 4

input.txt:

99999999999999

10

1 2 4 2 4 6 7 9

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n):

   if not(3<=n<=200000):
       print("Input-ul nu convine conditiilor")
       exit()

with open("input.txt", "r") as f, open("output.txt", "w") as g:

   n, fr, P, np, cer = [0] * 200010, [0] * 200010, [0] * 200010, 0, 0
   a, b, l, maxim, nm, i = 0, 0, 0, 0, 0, 0

   cer = int(f.readline())
   n = int(f.readline())
   verificare(n)
   a = int(f.readline(1))
   fr[a] += 1
   maxim = 1
   nm = a
   np = 0

   for line in f:
       for b in map(int, line.split()):
           fr[b] += 1

           if fr[b] > maxim:
               maxim = fr[b]
               nm = b
           elif fr[b] == maxim and b > nm:
               nm = b

           if l == 0 and b - a == 2:
               l = b - 1
           elif b - a != 1:
               np += 1
               P[np] = l
               l = 0

           a = b

   np += 1
   P[np] = l

   if cer == 1:
       g.write(f"{np}\n")
   elif cer == 2:
       g.write(f"{nm}\n")
   else:
       for i in range(1, np):
           g.write(f"{P[i]} ")
       g.write(f"{P[np]}\n")

</syntaxhighlight>