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ța

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.

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.

Exemplul 1

avarcolaciin.txt

3

2

1 4 3 4

1

1 1

3

4 1 4 4 4 4

avarcolaciout.txt

Mozart

1

4

Exemplul 2

avarcolaciin.txt

2

1

1 2

4

4 3 4 4 2 4

avarcolaciout.txt

1

4

Rezolvare

#1115 - Avarcolaci
def bantuie_satul(N, relationships):
    if not (1 <= N <= 500000):
        return "Fals"

    villagers = {}
    
    for i in range(2 * N):
        if not (1 <= relationships[i] <= 10**9):
            return "Fals"
        if relationships[i] not in villagers:
            villagers[relationships[i]] = []
        villagers[relationships[i]].append(i + 1)
    
    for v in villagers.keys():
        if len(villagers[v]) == N:
            return villagers[v][0]
    
    return "Mozart"

# Citirea datelor de intrare din fișierul "avarcolaciin.txt"
with open("avarcolaciin.txt", "r") as file:
    T = int(file.readline())
    tests = []
    
    for _ in range(T):
        N = int(file.readline())
        relationships = list(map(int, file.readline().split()))
        tests.append((N, relationships))

# Rezolvarea și scrierea rezultatelor în fișierul "avarcolaciout.txt"
with open("avarcolaciout.txt", "w") as file:
    for test in tests:
        result = bantuie_satul(*test)
        file.write(str(result) + "\n")

Explicatie

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.