Page 6 - MATINF Nr.2

6 D.A. Popescu, C. B˘alc˘au, D. Constantin

1. determinat , i cel mai mare divizor comun al numerelor din fiecare s , ir dat init , ial;
2. ajutat , i-o pe Adina s˘a afle, pentru fiecare din cele 3 s , iruri, dac˘a Mihai poate cˆas , tiga sau
nu (num˘arul k este acelas , i pentru toate s , irurile).

Date de intrare

Fis , ierul de intrare divgame.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe a doua linie se afl˘a num˘arul k.
Pe fiecare dintre urm˘atoarele 3 linii se afl˘a cˆate un num˘ar n, reprezentˆand dimensiunea
s , irului, urmat de n numere naturale nenule a 1 , a 2 , . . . , a n , reprezentˆand s , irul dat de Adina.

Date de ies , ire

Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire divgame.out se vor scrie 3 linii, linia i cont , inˆand un singur
num˘ar natural reprezentˆand cel mai mare divizor comun al numerelor din s , irul i, pentru i = 1, 3.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire divgame.out se vor afis , a 3 linii: pe linia i se va scrie mesajul
YES dac˘a Mihai poate cˆas , tiga pentru s , irul i, respectiv NO ˆın caz contrar, i = 1, 3.

Restrict , ii s , i preciz˘ari

1. 1 ≤ k ≤ 10 9
2. 1 ≤ dimensiunea s , irurilor ≤ 10 5
3. 1 ≤ elementele s , irurilor ≤ 10 9
4. Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj

Exemple

divgame.in divgame.out Explicat , ie
1 5 p = 1
6 7 cmmdc(10,15,30) = 5
3 10 15 30 1 cmmdc(7,49,21,35) = 7
4 7 49 21 35 cmmdc(33,1) = 1
2 33 1
divgame.in divgame.out Explicat , ie
2 YES p = 2
6 NO Mihai poate aduce primul s , ir
3 10 15 30 YES la forma 2 3 6, deci poate cˆas , tiga.
4 7 49 21 35 Al 2-lea s , ir nu poate fi adus
2 33 1 la un s , ir cu cmmdc 1 pentru k = 6.
Al 3-lea s , ir are deja cmmdc 1.

Timp maxim de execut , ie: 0.4 secunde/test.

Memorie total˘a disponibil˘a 4 MB.
Doru Anastasiu Popescu, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti