Editing 3196 - Instabook

Sursa: [https://www.pbinfo.ro/probleme/3196/instabook]
== Cerinţa ==
Gigel și-a făcut un nou cont pe Instabook. Imediat, a postat n poze, numerotate de la 1 la n, cu care s-a făcut un clasament în care poza 1 ocupă locul 1, poza 2 ocupă locul 2, …, poza n ocupă locul n. Fiecare dintre cei m prieteni ai lui Gigel dau like la o singură poză (prietenul i dă like la poza a[i], 1 ≤ i ≤ m).

Clasamentul pozelor de pe Instabook funcționează în felul următor: la un like dat unei poze, aceasta urcă în clasament cu un loc, cu excepția cazului în care este deja pe primul loc.

Gigel vrea să știe cel mai bun loc și cel mai slab loc din clasament pe care le-a ocupat fiecare poză.

== Date de intrare ==
Fișierul instabook.in va conține:

* pe prima linie se află n – numărul de poze și m – numărul de like-uri.

* pe a doua linie se află m numere naturale (1 ≤ număr ≤ n), fiecare reprezentând numărul de ordine al pozei care a primit like de la prietenul j, (1 ≤ j ≤ m).

== Date de ieșire == 
Fișierul '''instabook.out''' va conține n linii: pe linia i se vor afișa separate printr-un spațiu cel mai slab loc si cel mai bun loc din clasament al pozei i, (1 ≤ i ≤ n), iar în consolă se va afișa mesajul "Datele introduse corespund cerintelor." În caz contrar programul va afisa "Datele introduse nu corespund cerintelor."

== Restricţii şi precizări ==
* 1 &les; '''n''' &les; 100.000
* 1 &les; '''m''' &les; 200.000

== Exemplul 1 ==
; Intrare
: ''instabook.in''
: 3 5
: 3
: 2
: 1
: 3
: 3
; Ieșire
: Datele introduse corespund cerintelor.
: ''instabook.in''
: 1 2
: 2 3
: 1 3
<br>

== Exemplul 2 ==
; Intrare
: ''instabook.in''
: 0 0
: 0
: 0
: 0
: 0
: 0
; Ieșire
: Datele introduse nu corespund cerintelor.
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
#3196
NMAX = 100005


def validate_input(n, m):
    if not (1 <= n <= 100000):
        print("Datele introduse nu corespund cerintelor.")
        exit()
    if not (1 <= m <= 200000):
        print("Datele introduse nu corespund cerintelor.")
        exit()
    print("Datele introduse corespund cerintelor.")
    

def read_input(filename):
    with open(filename, "r") as fin:
        n, m = map(int, fin.readline().split())
        validate_input(n, m)
        a = [0] * NMAX
        p = [0] * NMAX
        ma = [0] * NMAX
        mi = [0] * NMAX
        for i in range(1, n + 1):
            a[i] = i
            p[i] = i
            ma[i] = i
            mi[i] = i
        for i in range(1, m + 1):
            x = int(fin.readline())
            if p[x] != 1:
                a1 = a[p[x] - 1]
                a2 = a[p[x]]
                a[p[x] - 1] = a2
                a[p[x]] = a1
                p[a1] += 1
                p[a2] -= 1
                ma[a1] = max(ma[a1], p[a1])
                mi[a2] = min(mi[a2], p[a2])
    return n, ma, mi


def write_output(filename, n, ma, mi):
    with open(filename, "w") as fout:
        for i in range(1, n + 1):
            fout.write(str(mi[i]) + ' ' + str(ma[i]) + '\n')


if __name__ == "__main__":
    n, ma, mi = read_input("instabook.in")
    write_output("instabook.out", n, ma, mi)

</syntaxhighlight>

== Explicatie rezolvare ==
Acest program citeste date de intrare dintr-un fisier '''instabook.in''' si apoi le valideaza prin intermediul functiei validate_input, care verifica daca n si m respecta limitele impuse de cerinta. Daca datele de intrare sunt invalide, se afiseaza un mesaj corespunzator si programul se opreste prin intermediul functiei '''exit()'''. Daca datele sunt valide, se afiseaza un mesaj corespunzator si programul continua executia.

In continuare, programul aloca cate o lista pentru a, p, ma si mi de dimensiune '''NMAX'''. Lista a retine ordinea initiala a elementelor, lista p retine pozitia curenta a fiecarui element, lista ma retine pozitia maxima pe care a fost gasit fiecare element si lista mi retine pozitia minima pe care a fost gasit fiecare element.

Urmeaza citirea efectiva a elementelor si executia operatiilor de interschimbare. Daca elementul citit nu se afla deja pe pozitia 1 (adica nu este primul element), se efectueaza interschimbarea elementelor aflate pe pozitiile p[x]-1 si p[x]. Dupa aceasta, pozitia fiecarui element modificat este actualizata in lista p, iar pozitia maxima si minima pe care a fost gasit fiecare element sunt actualizate in listele ma si mi.

In final, programul scrie datele de iesire in fisierul '''instabook.out''' utilizand functia '''write_output'''. Aceasta parcurge toate elementele si scrie, pentru fiecare dintre ele, valorile minime si maxime ale pozitiei acestora in listele mi si ma.