1115 - Avarcolaci

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din 2*N săteni, fiecare dintre aceștia fiind rudă cu exact un vârcolac. Vârcolacii sunt codificați cu numere naturale. Pentru a afla care este vârcolacul care le cauzează probleme, aceștia s-au dus la vraciul local. Acesta a spus că, dacă există un vârcolac V astfel încât oricum s-ar împărți cei 2*N săteni în două grupuri de N săteni, există cel puțin un sătean în primul grup și cel puțin un sătean în al doilea care să fie rude cu V, atunci vârcolacul V sigur este cel care bântuie satul. Dacă nu există un astfel de vârcolac, atunci sătenii nu își pot da seama cine le bântuie satul.

Cerință

Cunoscând N și indicii vârcolacilor cu care se înrudesc fiecare dintre cei 2*N săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.

Date de intrare

Fișierul de intrare avarcolaciIN.txt conține pe prima linie numărul T de teste. Următoarele 2*T linii conțin cele T teste. Prima linie dintr-un test conține numărul natural N, indicând faptul că avem 2*N săteni în Bosston. Următoarea linie conține 2*N elemente, al i-lea dintre aceste elemente reprezentând indicele vârcolacului cu care este rudă al i-lea sătean.

Date de ieșire

Fișierul de ieșire avarcolaciOUt.txt va conține T linii, câte una pentru fiecare test din fișierul de intrare. Dacă vârcolacul care bântuie satul nu poate fi determinat, atunci se va afișa textul ”Mozart” (fără ghilimele). Dacă vârcolacul poate fi determinat, atunci se va afișă indicele acestuia. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ T ≤ 15
• 1 ≤ N ≤ 500.000
• Pentru 10% din teste se garantează că N = 1
• Pentru 20% din teste se garantează că N < 10
• Pentru 40% din teste se garantează că N <= 500
• Pentru 80% din teste se garantează că N <= 50.000
• Indicii vârcolacilor sunt numere întregi pozitive mai mici ca 109
• Pentru 50% din teste indicii vârcolacilor sunt mai mici strict ca 32762
• ATENȚIE! Satul conține 2*N săteni!
• ATENȚIE la limita de memorie!
• ATENȚIE! În cazul în care sunt mai multe soluții pentru vârcolacul care bântuie satul, se acceptă oricare dintre ele.

Exemplu 1:

avarcolaciIN.txt

3
2
1 4 3 4
1
1 1
3
4 1 4 4 4 4

avarcolaciOUT.txt

Mozart
1
4

Explicație

1. Dacă împărțim în grupuri vârcolacii asociați celor 4 săteni obținem (1, 3) (4, 4) și nu avem un vârcolac atât în primul grup, cât și în al doilea.
2. Vârcolacul 1 bântuie satul.
3. Vârcolacul 4 bântuie satul – nu putem împărți sătenii în două grupuri astfel încât 4 să nu fie în niciunul dintre ele.

Exemplu 2:

avarcolaciIN.txt

16
2
1 4 3 4
1
1 1
3
4 1 4 4 4 4

avarcolaciOUT.txt

Datele nu corespund restrictiilor impuse 

Rezolvare

<syntaxhighlight lang="python" line="1"> def verifica_restrictii(nr_teste, n, el):

   TMAX = 15
   NMAX = 500000
   EL_MAX = int(1e9)

   if not (1 <= nr_teste <= TMAX):
       return False
   if not (1 <= n <= NMAX):
       return False
   if not (0 <= el <= EL_MAX):
       return False

   return True

def main():

   with open("avarcolaciIN.txt", "rt") as f_in, open("avarcolaciOUt.txt", "wt") as f_out:
       nr_teste = int(f_in.readline().strip())

       if not verifica_restrictii(nr_teste, 1, 0):
           f_out.write("Datele nu corespund restrictiilor impuse\n")
           return

       potential = [0] * (nr_teste + 1)

       for test in range(1, nr_teste + 1):
           n = int(f_in.readline().strip())
           if not verifica_restrictii(1, n, 0):
               f_out.write("Datele nu corespund restrictiilor impuse\n")
               return

           maj, cnt = -1, 0

           elements = list(map(int, f_in.readline().split()))
           if not all(verifica_restrictii(1, 1, el) for el in elements):
               f_out.write("Datele nu corespund restrictiilor impuse\n")
               return

           for el in elements:
               if maj == -1:
                   maj = el
                   cnt = 1
               else:
                   if el == maj:
                       cnt += 1
                   else:
                       cnt -= 1
                       if cnt == 0:
                           maj = el
                           cnt = 1

           potential[test] = maj

   with open("avarcolaciIN.txt", "rt") as f_in:
       nr_teste = int(f_in.readline().strip())

       for test in range(1, nr_teste + 1):
           n = int(f_in.readline().strip())
           elements = list(map(int, f_in.readline().split()))

           cnt = 0
           for x in elements:
               if x == potential[test]:
                   cnt += 1

           with open("avarcolaciOUt.txt", "a") as f_out:
               if cnt > n:
                   f_out.write(f"{potential[test]}\n")
               else:
                   f_out.write("Mozart\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>