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 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 ș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 10⁹
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

avarcolaci.in

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

avarcolaci.out

Mozart
1
4

Explicație

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.
Vârcolacul 1 bântuie satul.
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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Avarcolaci:

/* Andrei Parvu
   ONI 2014
*/

#include <cstdio>
#include <cassert>
#include <algorithm>

using namespace std;

const int NMAX = 500000;
const int TMAX = 15;
const int EL_MAX = 1e9;

int potential[TMAX];

int main() {
  freopen("avarcolaci.in", "rt", stdin);
  freopen("avarcolaci.out", "wt", stdout);

  int nrTests;

  scanf("%d", &nrTests);

  assert(1 <= nrTests && nrTests <= TMAX);

  for (int test = 1; test <= nrTests; test++) {
    int n;

    scanf("%d", &n);
    assert(1 <= n && n <= NMAX);
    int maj = -1, cnt = 0;

    for (int i = 0; i < 2 * n; i++) {
      int el;
      scanf("%d", &el);

      assert(0 <= el && el <= EL_MAX);

      if (maj == -1) {
        maj = el;
        cnt = 1;
      } else {
        if (el == maj) {
          cnt++;
        } else {
          cnt--;

          if (cnt == 0) {
            maj = el;
            cnt = 1;
          }
        }
      }
    }

    potential[test] = maj;
  }

  fclose(stdin);
  freopen("avarcolaci.in", "rt", stdin);

  scanf("%d", &nrTests);

  for (int test = 1; test <= nrTests; test++) {
    int n;

    scanf("%d", &n);

    int cnt = 0;
    for (int i = 0; i < 2 * n; i++) {
      int x;
      scanf("%d", &x);

      if (x == potential[test]) {
        cnt++;
      }
    }

    if (cnt > n) {
      printf("%d
", potential[test]);
    } else {
      // Problema e mai clasica ca Mozart
      printf("Mozart
");
    }
  }

  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1115 Avarcolaci

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1115 Avarcolaci de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1115 Avarcolaci