Fişierul intrare/ieşire:avarcolaci.in, avarcolaci.outSursăONI 2014 Clasele 11-12
AutorAndrei ParvuAdăugată deMihai22eMihai Ionut Enache Mihai22e
Timp execuţie pe test6 secLimită de memorie7168 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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şierului de intrare avarcolaci.in 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 avarcolaci.out 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

  • 1 ≤ T15
  • 1 ≤ N500.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 32.762
  • 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

avarcolaci.inavarcolaci.out
3
2
1 4 3 4
1
1 1
3
4 1 4 4 4 4
Mozart
1
4

Explicaţie

1. Dacă împăţ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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content