Editing 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 <code>N</code> nivele, numerotate consecutiv de la <code>1</code> la <code>N</code>, î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 <code>N-1</code> ș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 <code>P</code> și a sărit peste un nivel <code>L</code> (<code>P < L < P + K</code>), finalizând <code>K</code> nivele memorate ca o succesiune de numere naturale de forma <code>P, P+1,..., L-1, L+1,..., P+K</code>. Succesiunile de nivele finalizate de participanți au fost memorate în fișierul <code>input.txt</code>. 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 <code>input.txt</code> conţine pe prima linie una dintre valorile <code>1</code> , <code>2</code> sau <code>3</code>, 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 <code>N</code> 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 <code>output.txt</code> va conţine pe prima linie un număr natural <code>M</code>, 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 <code>M</code> 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 =

* <code>3 ≤ N ≤ 200000</code>.

== 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: <code>1 2 4</code> (primul), <code>2 4</code> (al doilea) şi <code>6 7 9</code> (al treilea).

== Exemplul 2 ==
input.txt:

2

10

1 2 4 2 4 6 7 9

output.txt:

4

Explicație:

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

== 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 <code>3</code>, al doilea nivelul <code>3</code>, iar al treilea nivelul <code>8</code>.

== 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>