Page 6 - MATINF Nr.2
P. 6

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
   1   2   3   4   5   6   7   8   9   10   11