Cupa InfoAs, ediția 7 · Clasa a IX-aOperații cu bițiProbleme cu operații cu biți
Problema Trigon cu vanilie
Dacă Matei ar avea bani infiniți, credeți-mă pe cuvânt că nu și-ar lua altceva decât patiserii cu vanilie. Nu contează forma, mărimea sau procentajul de vanilie, atât timp cât simte gustul dulce al ingredientului lui preferat, Matei va fi încântat pentru tot restul zilei. Dar admirația lui foarte specifică pentru vanilie este cu atât mai mare când are ocazia de a mânca un trigon cu vanilie, preparat chiar de către bunicul său.
Dorința de îmbogățire, laitmotiv în categoria sa de vârstă, îl determină într-o zi pe Matei să își deschidă o patiserie în care să vândă — ghiciți ce — patiserii cu vanilie. Neștiind rețeta secretă a bunicului, însă, Matei se gândește să intre în calculatorul bunicului său pentru a găsi rețeta.
Bunicul său, mare iubitor de matematică (?) are un întreg sistem de reținere a parolelor în caz că le uită. Desigur, parola este un număr natural, însă sunt atât de multe opțiuni încât n-ai putea să ghicești parola așa ușor.
Ca să găsim parola, procedăm în felul următor: imaginați-vă o matrice inițial nulă. Acesta are, mai apoi, o listă cu mai multe perechi de numere x și y, iar în matricea sa, pentru fiecare astfel de pereche, adună 1 la elementul de pe linia x și coloana y. Intenționat, bunicul s-a asigurat ca, după completarea matricei, pe fiecare linie x, exact o singură coloană are numărul asociat o valoare impară.
Luăm fiecare astfel de coloană y și adunăm valorile. Aceasta este parola bunicului său.
Cerință
Se dau numere naturale n, m și k, împreună cu lista de perechi x și y. Considerând că matricea are n linii și m coloane și că lista conține k perechi de numere, să se determine parola bunicului.
Date de intrare
Fișierul de intrare vanilie.in conține pe prima linie numerele naturale n, m și k separate prin câte un spațiu. Pe următoarele k linii se află câte două numere naturale separate printr-un spațiu, x și y, reprezentând elementele listei.
Date de ieșire
Fișierul de ieșire vanilie.out conține un singur număr natural, reprezentând parola bunicului lui Matei. Dacă o găsești, Matei te așteaptă la el la patiserie cu un trigon cu vanilie și te trece pe caiet.
Restricții și precizări
- Pentru fiecare pereche de numere,
1 ≤ x ≤ n,1 ≤ y ≤ m - Se garantează că matricea completă are un singur număr impar pe fiecare linie
- Elementele matricei sunt indexate de la
1 1 ≤ k ≤ 100.000
Subtask 1 (40 de puncte)
1 ≤ n, m ≤ 1000
Subtask 2 (60 de puncte)
1 ≤ n, m ≤ 100.000
Exemplu
2 3 6 1 1 2 3 1 2 2 3 2 3 1 1
5
Explicația exemplului
Matricea rezultată are elementele de pe prima linie 2 1 0 și pe a doua linie 0 0 3. Coloanele cu elemente impare sunt 2 și 3. Prin urmare, parola este 2 + 3 = 5.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;