Gina şi Mihai joacă împreună jocul Cuarţ. Ei au la dispoziţie un şir de 2*N cartonaşe ce conţin numere naturale. Primele N cartonaşe, de la stânga la dreapta, sunt ale Ginei, iar următoarele N ale lui Mihai. Gina traveresează şirul, de la stânga la dreapta şi scrie pe o foaie de hârtie, pe primul rând, un şir de numere obţinut din numerele de pe cartonaşele sale, din care a şters toate cifrele pare. La fel procedează Mihai care scrie pe foaia sa de hârtie, pe primul rând, şirul de numere obţinut din numerele de pe cartonaşele sale, din care a şters toate cifrele impare. Dacă dintr-un număr s-au şters toate cifrele, sau au rămas doar cifre egale cu 0, atunci numărul este ignorat, deci pe hârtie nu se scrie nimic.
Fiecare copil, notează pe hârtia sa, pe al doilea rând, un alt şir de numere obţinut astfel: pentru fiecare număr X scris pe primul rând, copilul va scrie cel mai mare număr natural K cu proprietatea că 1+5+9+13+...+ K ≤ X. În jocul copiilor, numărul X se numeşte cuarţ dacă 1+5+9+13+...+K = X .
În exemplul de mai sus, Gina nu a scris niciun număr cuarţ pe primul rând, iar Mihai a scris unul singur (6=1+5).
Regulile de câştig ale jocului sunt următoarele:
• Câştigă acel copil care are scrise pe primul rând cele mai multe numere cuarţ. În acest caz, valoarea de câştig a jocului este egală cu numărul de numere cuarţ scrise de copilul câştigător.
• Dacă cei doi copii au scris acelaşi număr de numere cuarţ, atunci va câştiga cel care are primul număr scris pe primul rând, mai mare decât al celuilalt. Acest prim număr scris de câştigător va reprezenta valoarea de câştig.
• Dacă nici Gina şi nici Mihai nu au scris niciun număr pe hârtie, se consideră egalitate şi nu câştigă niciunul.
Cerinţă
Scrieţi un program care să citească numărul N reprezentând numărul de cartonaşe ale unui copil şi cele 2*N numere de pe cartonaşe, în ordine de la stânga la dreapta şi care să determine:
1) Cel mai mare număr de pe cele 2*N catonaşe, pentru care nu s-a scris niciun număr pe primul rând (a fost omis), nici pe hârtia Ginei, nici pe hârtia lui Mihai; dacă nu a fost omis niciun număr, se va scrie 0;
2) Câştigătorul jocului şi afişează numărul 1 dacă a câştigat Gina, 2 pentru Mihai sau 0 în caz de egalitate.
3) Valoarea de câştig a jocului, sau 0, în caz de egalitate.
Date de intrare
Fişierul de intrare cuart.in conţine pe prima linie un număr natural P. Pentru toate testele de intrare, numărul P poate avea doar valoarea 1, valoarea 2 sau valoarea 3. Pe a doua linie a fişierului de intrare cuart.in se găseşte numărul natural N reprezentând numărul de cartonaşe ale fiecărui copil şi pe a treia linie, în ordine de la stânga la dreapta, numerele de pe cele 2*N cartonaşe, separate prin câte un spaţiu.
Date de ieşire
Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerinţe. În acest caz, fişierul de ieşire cuart.out va conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa 1).
Dacă valoarea lui P este 2, se va rezolva numai punctul 2) din cerinţe. În acest caz, fişierul de ieşire cuart.out va conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa 2).
Dacă valoarea lui P este 3, se va rezolva numai punctul 3) din cerinţe. În acest caz, fişierul de ieşire cuart.out va conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa 3).
Restricţii
• 1 ≤ N ≤ 1000
• 1 ≤ numerele de pe cartonaşe < 100000000
Exemple
cuart.in
cuart.out
Explicaţii
1
4
1234 48 284260 75 756 1232515 153 98
284260
P = 1, pentru acest test, se rezolvă cerinţa 1).
Gina a scris pe hârtia sa, pe două rânduri numerele:
13 75
5 21
Mihai a scris pe hârtie numerele:
6 22 8
5 9 5
Cel mai mare număr omis este 284260
2
4
1234 48 284260 75 756 1232515 153 98
2
P = 2, pentru acest test, se rezolvă cerinţa 2).
A câştigat Mihai deoarece are un număr cuarţ, iar Gina niciunul
3
1
154 2181
28
P = 3, pentru acest test, se rezolvă cerinţa 3).
Gina a scris pe hârtia sa, pe două rânduri numerele:
15
9
Mihai a scris pe hârtie numerele:
28
13
Ambii copii au scris câte un număr cuarţ, însă a câştigat Mihai care are primul număr scris pe primul rând mai mare decât al Ginei. Valoarea de câştig a jocului este 28.
