Fişierul intrare/ieşire:game4.in, game4.outSursăConcursul Naţional de Informatică Urmaşii lui Moisil 2017
AutorCristian Vintur, Liana Tucar, Paul DiacAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test2 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Game4

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 a1 a2 ... aN . O mutare constă în alegerea unui număr de forma pk , unde p este un număr prim iar k un număr natural nenul, urmată de împărţirea prin pk a tuturor numerelor ai care se divid cu această valoare (trebuie să existe în şirul curent cel puţin o valoare ai 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 ai 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ă.

Cerinţă

  1. Determinaţi câştigătorul jocului.
  2. 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 pk 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 pk 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 pk 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.

Date de intrare

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 a1 a2 ... aN separate prin câte un spaţiu. Pentru toate testele din acelaşi fişier se rezolvă aceeaşi cerinţă C.

Date de ieşire

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.

Restricţii

  • 2 < T < 10
  • 1 < N < 100.000
  • 1 < ai < 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, ai < 20, 1 < i < N

Exemplu

game4.ingame4.out
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

Explicaţie

Sunt 4 teste de rezolvat pe cerinţa 1.
În primul joc, N=2 şi a1 = 7, a2 = 25 şi câştigă Alice.
Ea poate alege iniţial pk = 51, pk = 52 sau pk = 71 . Pot avea loc variantele:

  • pk = 51, împarte la 51 valorile şi obţine a1 = 7 şi a2 = 5. Dacă acum Bob alege 7 se obţine a1 = 1 şi a2 = 5. Alice va alege 5, se va obţine a1 = 1 şi a2 = 1 şi ea va câştiga. Analog s-ar fi întâmplat dacă Bob ar fi ales 5 în loc de 7.
  • Cazurile pk = 52 sau pk = 71 pentru prima mutare a lui Alice îi vor permite lui Bob să aleagă fie 7 fie 52 şi să câştige. În concluzie, Alice câştigă numai dacă alege pk = 51.

În al doilea joc, N=2 şi a1 = 10, a2 = 21 şi câştigă Bob.
Alice poate alege iniţial pk = 21, pk = 51, pk = 31 şi pk = 71. 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.

game4.ingame4.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

Explicaţie

Sunt 4 teste de rezolvat pe cerinţa 2 (vezi explicaţia de mai sus).
În primul joc, N=2 şi a1 = 7, a2 = 25 şi câştigă Alice, care poate alege iniţial doar varianta pk = 51 care îi permite să câştige. Aşadar, sunt V = 1 variante distincte.
În al doilea joc, dacă Alice alege pk = 21 , Bob poate alege iniţial pk = 51 , pk = 31 sau pk = 71. Similar, dacă Alice alege oricare dintre pk = 51, pk = 31 sau pk = 71 , 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, pk = 31 în toate cele trei cazuri când Alice a ales iniţial pk = 21 sau pk = 51 sau pk = 71, dar această mutare se numără o singură dată.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?