2965 - album

Victor și Radu sunt frați. Mama le-a adus n stickere cu fotbaliști, fiecare sticker având imprimat pe spate un cod, un număr cuprins între 10 și 999.999. Frații, dorind cât mai multe stickere pe care să le lipească în albumul propriu, au început să se certe. Mama le propune următorul mod de împărțire a stickerelor: ea aranjează cele n stickere în linie, cu fața în jos, iar apoi fiecare frate, pe rând, va lua primul sticker disponibil, precum și toate stickerele care conțin două cifre care sunt egale cu cele mai mari două cifre, nu neapărat distincte, dintre cele scrise pe primul sticker luat la această etapă. Stickerele sunt disponibile începând de la stânga la dreapta. Fiind cel mai mic, Victor va fi primul, apoi copiii iau stickere alternativ, până când nu mai sunt stickere. La final, fiecare copil numără câte stickere are în total.

Cerințe

Cunoscându-se numărul n de stickere aduse de mama și numerele de pe ele în ordinea în care sunt așezate pe masă, să se determine:

1. Cele mai mari două cifre, nu neapărat distincte, de pe ultimul sticker aflat pe masă înainte de începerea concursului;

2. Fratele care câștigă concursul și câte stickere are.

Date de intrare

Fișierul de intrare album.in conține pe prima linie o cifră c care poate să fie doar 1 sau 2. Pe a doua linie se găsește n reprezentând numărul de stickere. Pe a treia linie se află n numere naturale separate prin câte un spațiu, reprezentând numerele de pe stickere.

Date de ieșire

Dacă valoarea lui c este 1, atunci se va rezolva numai punctul 1 din cerință. În acest caz, fișierul de ieșire album.out va conține pe prima linie, în ordine crescătoare, cifrele cerute.

Dacă valoarea lui c este 2, atunci se va rezolva numai punctul 2 din cerință. În acest caz, fişierul de ieşire album.out va conține pe prima linie litera V dacă Victor are mai multe stickere, litera R dacă Radu are mai multe stickere, sau literele V și R separate prin exact un spațiu dacă amândoi au același număr de stickere. Pe a doua linie se va scrie numărul de stickere ale celui care are cele mai multe sau numărul de stickere deținut de fiecare, în cazul în care au același număr de stickere.

Restricții și precizări

• 3 ≤ n ≤ 800 000;
• Pentru cerința 2 se garantează că, pentru 50% din teste, n ≤ 100;
• Rezolvarea cerinței 1 garantează 40p, iar cerința 2 garantează 50p;
• În concurs au fost acordate 10p din oficiu. Pe site se cere rezolvarea exemplelor.

Exemplul 1:

album.in

1
7
291 11 992 456 71 13 121

album.out

1 2

Explicație

Cerința este 1. Pe ultimul sticker de pe masă este scris numărul 121, care are cele mai mari două cifre 1 și 2.

Exemplul 2:

album.in

2
7
234 122 334 199 463 221 231 

album.out

V
4

Explicație

Cerința este 2. Victor începe concursul și ia stickerele 234 (cu 3 și 4 cele mai mari două cifre), 334 și 463. Pe masă rămân stickerele 122 199 221 231. Continuă Radu, care ia stickerele cu numerele 122 (cu cele mai mari două cifre 2 și 2) și 221. Rămân stickerele 199 și 231. Victor mai ia stickerul cu numărul 199, apoi Radu ia stickerul cu numărul 231. Victor câștigă cu 4 stickere, Radu având doar 3.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import numpy as np

v = np.zeros(8) ord = np.zeros(100) w = np.zeros(10, dtype=np.int16)

def main():

   with open("album.in", "r") as f, open("album.out", "w") as g:
       i, j, N, n, x, z, poz = 0, 0, 0, 0, 0, 0, 0
       Mm, ii, ORD = 0, 0, 0
       p = 0
       a = [] * 20
       V, R = 0, 0

       p = int(f.readline())
       N = int(f.readline())

       if p == 1:
           for ii in range(1, N + 1):
               a = f.readline()
           for j in range(len(a)):
               x = int(a[j]) - 0
               w[x] += 1
           i = 0
           for j in range(9, -1, -1):
               if w[j] >= 1:
                   i += 1
                   v[i] = j
           x = v[1]
           if w[x] > 1:
               g.write(str(x) + " " + str(x))
           else:
               g.write(str(v[2]) + " " + str(v[1]))

           return 0

       for ii in range(1, N + 1):
           a = f.readline()
           for j in range(10):
               w[j] = 0
           for j in range(len(a)):
               x = int(a[j]) - 0
               w[x] += 1
           i = 0
           for j in range(9, -1, -1):
               if w[j] >= 1:
                   i += 1
                   v[i] = j
           n = i
           x = v[1]
           if w[x] > 1:
               Mm = x * 10 + x
           else:
               Mm = v[1] * 10 + v[2]
           ORD = 1234567
           for i in range(1, n + 1):
               x = v[i]
               if w[x] > 1:
                   z = x * 10 + x
                   if ord[z] > 0:
                       if ord[z] < ORD:
                           ORD = ord[z]
           for i in range(1, n):
               for j in range(i + 1, n + 1):
                   z = v[i] * 10 + v[j]
                   if ord[z] > 0:
                       if ord[z] < ORD:
                           ORD = ord[z]
           if ORD == 1234567:
               poz += 1
               ord[Mm] = poz
               ORD = poz
               if poz % 2:
                   V += 1
               else:
                   R += 1
           else:
               if ORD % 2:
                   V += 1
               else:
                   R += 1

       if V > R:
           g.write("V\n" + str(V))
       elif R > V:
           g.write("R\n" + str(R))
       else:
           g.write("V R\n" + str(V))

       return 0

if __name__ == '__main__':

    main()

</syntaxhighlight>