2525 - Cioc

Cioc

Cioc, un elev abia aterizat în clasa a IX-a, primește de la doamna profesor de informatică un șir de n numere naturale pe care trebuie să îl prelucreze. Astfel, băiatul trebuie să scrie după fiecare dintre cele k cele mai mici elemente dublul lor. Dacă cel mai mare dintre aceste numere se repetă și deja se depășesc cele k elemente prevăzute, doamna profesor îi dă libertatea băiatului de a modifica valoarea lui k astfel încât să cuprindă și aceste valori. De exemplu, dacă n = 7, v[] = {1, 4, 6, 2, 3, 4, 5} și k = 4, atunci, în urma prelucrării, șirul v devine {1, 2, 4, 8, 6, 2, 4, 3, 6, 4, 8, 5}, și deci kfinal=5.

Cerința

Cunoscându-se n, șirul v și k, să se afișeze:

• 1. Numărul kfinal;
• 2. Vectorul după prelucrare.

Date de intrare

Fișierul de intrare ciocin.txt conține pe prima linie numerele c (mereu 1 sau 2, reprezentând cerința ce trebuie rezolvată), n, k, iar următoarea linie va conține n numere întregi, reprezentând elementele vectorului inițial.

Date de ieșire

Fișierul de ieșire ciocout.txt va conține pe prima linie:

• Dacă c = 1, atunci numărul kfinal;
• Dacă c = 2, atunci vectorul după prelucrare.

Restricții și precizări

• 1 ≤ n, k ≤ 100.000;
• 1≤v[i]≤2^60;
• Pentru 40% din teste, c=1.

Exemplul 1

ciocin.txt

1 7 4

1 4 6 2 3 4 5

ciocout.txt

Datele introduse corespund restricțiilor impuse.

5

Explicație

k-ul inițial nu este suficient de cuprinzător (numărul 4 se repetă).

Exemplul 2

ciocin.txt

2 7 4

1 4 6 2 3 4 5

ciocout.txt

Datele introduse corespund restricțiilor impuse.

1 2 4 8 6 2 4 3 6 4 8 5

Explicație

Acesta este exemplul din enunț.

Exemplul 3

ciocin.txt

2 7 4

1 4 6 2 3 4 1000000001

ciocout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 2525 - Cioc

def validare(n_validare, k_validare, sir_validare): # functia de validare a datelor de intrare

   if not (1 <= n_validare <= 100000 and 1 <= k_validare <= 100000):
       raise ValueError

   for v in sir_validare:
       if not (1 <= v <= 260):
           raise ValueError

   fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def prelucrare(n_prelucrare, k_prelucrare, sir_prelucrare): # functia de rezolvare a problemei

   sir_sortat = sorted([(v, i) for i, v in enumerate(sir_prelucrare)])
   k_final_prelucrare = k_prelucrare
   while k_final_prelucrare < n_prelucrare and sir_sortat[k_final_prelucrare][0] == sir_sortat[k_prelucrare-1][0]:
       k_final_prelucrare += 1

   sir_prelucrat_prelucrare = []
   for v, i in sir_sortat[:k_final_prelucrare]:
       sir_prelucrat_prelucrare.append((i, v))
       sir_prelucrat_prelucrare.append((i, v*2))
   sir_prelucrat_prelucrare.sort()

   return k_final_prelucrare, [v for i, v in sir_prelucrat_prelucrare]

if __name__ == '__main__':

   fisier_intrare = open("ciocin.txt", "r")         # declararea fisierelor
   fisier_iesire = open("ciocout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       c, n, k = map(int, fisier_intrare.readline().split())
       sir = list(map(int, fisier_intrare.readline().split()))

       validare(n, k, sir)                 # apelul functiei de validare

       k_final, sir_prelucrat = prelucrare(n, k, sir)  # apelul functiei de rezolvare

       if c == 1:
           fisier_iesire.write(str(k_final) + "\n")
       else:
           fisier_iesire.write(" ".join(map(str, sir_prelucrat)) + "\n")

   except ValueError:
       fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>