3196 - Instabook

Sursa: [1]

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 ⩽ n ⩽ 100.000
1 ⩽ m ⩽ 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

Exemplul 2

Intrare: instabook.in; 0 0; 0; 0; 0; 0; 0
Ieșire: Datele introduse nu corespund cerintelor.

Rezolvare

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 primește ca date de intrare un număr întreg n, un număr întreg k și o listă v de n numere întregi și sortează primii k elemente ai listei v în ordine crescătoare, folosind o implementare a algoritmului de sortare prin selecție.

Funcțiile read_input_file și write_output_file se ocupă de citirea datelor de intrare din fișierul cu extensia ".in" și scrierea datelor de ieșire în fișierul cu extensia ".out". Funcția min_element_index returnează indexul elementului minim dintr-un interval specificat, iar funcția sort_k_elements sortează primii k elemente ai listei v.

Funcția validate_input verifică dacă datele de intrare corespund cerințelor. Dacă valorile n și k nu sunt între 1 și 1000, respectiv 1 și n(n-1)/2, funcția afișează un mesaj corespunzător și programul se încheie. În caz contrar, funcția afișează un mesaj corespunzător și programul continuă cu sortarea listei v.