Editing 1115 - Avarcolaci

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din <code>2*N</code> 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 <code>V</code> astfel încât oricum s-ar împărți cei <code>2*N</code> săteni în două grupuri de <code>N</code> 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 <code>V</code>, atunci vârcolacul <code>V</code> 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 <code>N</code> și indicii vârcolacilor cu care se înrudesc fiecare dintre cei <code>2*N</code> săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.

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

= Date de ieșire =
Fișierul de ieșire <code>avarcolaciOUt.txt</code> va conține <code>T</code> 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 =

* <code>1 ≤ T ≤ 15</code>
* <code>1 ≤ N ≤ 500.000</code>
* Pentru 10% din teste se garantează că <code>N = 1</code>
* Pentru 20% din teste se garantează că <code>N < 10</code>
* Pentru 40% din teste se garantează că <code>N <= 500</code>
* Pentru 80% din teste se garantează că <code>N <= 50.000</code>
* Indicii vârcolacilor sunt numere întregi pozitive mai mici ca <code>109</code>
* Pentru 50% din teste indicii vârcolacilor sunt mai mici strict ca <code>32762</code>
* ATENȚIE! Satul conține <code>2*N</code> 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: =
<code>avarcolaciIN.txt</code>
 3
 2
 1 4 3 4
 1
 1 1
 3
 4 1 4 4 4 4
<code>avarcolaciOUT.txt</code>
 Mozart
 1
 4

= Explicație =

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

== Exemplu 2: ==
<code>avarcolaciIN.txt</code>
 16
 2
 1 4 3 4
 1
 1 1
 3
 4 1 4 4 4 4
<code>avarcolaciOUT.txt</code>
 Datele nu corespund restrictiilor impuse 
<br>
== 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>