== include(page="template/taskheader" task_id="game4") ==
Poveste şi cerinţă...
Alice si Bob joacă un joc matematic în care cei doi mută alternativ. Iniţial, ei pornesc jocul cu un şir de $N$ numere naturale nenule $a{~1~} a{~2~} ... a{~N~}$ . O mutare constă în alegerea unui număr de forma $p^k^$ , unde $p$ este un număr prim iar $k$ un număr natural nenul, urmată de împărţirea prin $p^k^$ a tuturor numerelor $a{~i~}$ care se divid cu această valoare (trebuie să existe în şirul curent cel puţin o valoare $a{~i~}$ care va fi modificată în această etapă). Alice face mereu prima mutare. Câştigă cel care realizează ultima mutare, iar cel care nu mai poate muta, pierde (toate valorile $a{~i~}$ au devenit $1$). La fiecare mutare, dacă jucătorul curent are strategie de câştig, va juca aplicând acestă strategie. În caz contrar, jucătorul este nevoit să facă o mutare posibilă.
h2. Cerinţă
# Determinaţi câştigătorul jocului.
# Determinaţi numărul $V$ de variante distincte de a face prima mutare, pentru jucătorul care câştigă jocul. De exemplu, presupunând că Alice câştigă, $V$ = numărul de valori $p^k^$ distincte, pe care le poate alege Alice la prima ei mutare, astfel încât să fie sigură că va câştiga jocul în final. Presupunând că Bob va câştiga jocul, $V =$ numărul de valori $p^k^$ distincte, dintre care poate alege Bob la prima lui mutare, astfel încât el să câştige în final (nu uitaţi că Alice începe jocul). Dacă Bob poate alege aceeaşi valoare $p^k^$ pentru două variante diferite ale mutării iniţiale a lui Alice, valoare care l-ar duce la câştig, se va număra o singură dată această valoare.
h2. Date de intrare
Fişierul de intrare $game4.in$ ...
Fişierul de intrare $game4.in$ conţine $T$ teste. Pe prima linie se află numerele naturale $T$ şi $C$, numărul de teste, respectiv cerinţa ({$1$} sau $2$). Următoarele $T$ linii conţin câte un joc dat prin $N$ şi numerele $a{~1~} a{~2~} ... a{~N~}$ separate prin câte un spaţiu. Pentru toate testele din acelaşi fişier se rezolvă aceeaşi cerinţă $C$.
h2. Date de ieşire
În fişierul de ieşire $game4.out$ ...
Fişierul de ieşire $game4.out$ va conţine $T$ linii, pe linia i va fi răspunsul pentru testul al $i$-lea.
Dacă $C = 1$, se afişează pentru fiecare joc, numele câştigătorului *„Alice”* sau *„Bob”*.
Dacă $C = 2$, se afişează pentru fiecare joc, numărul $V$ de mutări distincte dintre care câştigătorul ar putea alege prima sa mutare, conform precizărilor de la punctul $2$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 < T < 10$
* $1 < N < 100.000$
* $1 < a{~i~} < 1.000.000,1 < i < N$
* $Pentru teste în valoare de 40 puncte, C = 1.$
* $Pentru teste în valoare de 60 puncte, C = 2. Pentru o parte dintre acestea, în valoare de 20 puncte, Alice câştigă întotdeauna.$
* $Pentru teste în valoare de 30 puncte, a{~i~} < 20, 1 < i < N$
h2. Exemplu
table(example). |_. game4.in |_. game4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 1
2 7 25
2 10 21
10 43 89 47 29 68 2 27 52 92 27
7 23 1 529 19 1 529 29
| Alice
Bob
Alice
Bob
|
h4. Explicaţie
Sunt $4$ teste de rezolvat pe cerinţa $1$.
În primul joc, $N=2$ şi $a{~1~} = 7$, $a{~2~} = 25$ şi câştigă Alice.
Ea poate alege iniţial $p^k^ = 5^1^$, $p^k^ = 5^2^$ sau $p^k^ = 7^1^$ . Pot avea loc variantele:
* $p^k^ = 5^1^$, împarte la $5^1^$ valorile şi obţine $a{~1~} = 7$ şi $a{~2~} = 5$. Dacă acum Bob alege $7$ se obţine $a{~1~} = 1$ şi $a{~2~} = 5$. Alice va alege $5$, se va obţine $a{~1~} = 1$ şi $a{~2~} = 1$ şi ea va câştiga. Analog s-ar fi întâmplat dacă Bob ar fi ales $5$ în loc de $7$.
* Cazurile $p^k^ = 5^2^$ sau $p^k^ = 7^1^$ pentru prima mutare a lui Alice îi vor permite lui Bob să aleagă fie $7$ fie $5^2^$ şi să câştige. În concluzie, Alice câştigă numai dacă alege $p^k^ = 5^1^$.
În al doilea joc, $N=2$ şi $a{~1~} = 10$, $a{~2~} = 21$ şi câştigă Bob.
Alice poate alege iniţial $p^k^ = 2^1^$, $p^k^ = 5^1^$, $p^k^ = 3^1^$ şi $p^k^ = 7^1^$. Pentru fiecare alegere a lui Alice, Bob poate alege oricare dintre celelalte trei variante rămase. În următoarele două mutări, o alegere va fi a lui Alice şi ultima valoare va fi aleasă de Bob, care va câştiga.
table(example). |_. game4.in |_. game4.out |
| 4 2
2 7 25
2 10 21
10 43 89 47 29 68 2 27 52 92 27
7 23 1 529 19 1 529 29
| 1
4
1
4
|
h3. Explicaţie
h4. Explicaţie
...
Sunt $4$ teste de rezolvat pe cerinţa $2$ (vezi explicaţia de mai sus).
În primul joc, $N=2$ şi $a{~1~} = 7$, $a{~2~} = 25$ şi câştigă Alice, care poate alege iniţial doar varianta $p^k^ = 5^1^$ care îi permite să câştige. Aşadar, sunt $V = 1$ variante distincte.
În al doilea joc, dacă Alice alege $p^k^ = 2^1^$ , Bob poate alege iniţial $p^k^ = 5^1^$ , $p^k^ = 3^1^$ sau $p^k^ = 7^1^$. Similar, dacă Alice alege oricare dintre $p^k^ = 5^1^$, $p^k^ = 3^1^$ sau $p^k^ = 7^1^$ , Bob va putea alege prima mutare dintre celelalte $3$ variante rămase. În concluzie, numărul de valori distincte pe care Bob le poate alege iniţial este $V = 4$.
Observăm că Bob poate alege ca primă mutare, $p^k^ = 3^1^$ în toate cele trei cazuri când Alice a ales iniţial $p^k^ = 2^1^$ sau $p^k^ = 5^1^$ sau $p^k^ = 7^1^$, dar această mutare se numără o singură dată.
== include(page="template/taskfooter" task_id="game4") ==
