Page 7 - MATINF Nr.2
P. 7
Concursul de Informatic˘a Programming Day 7
Solut , ie
ˆ
In rezolvarea primei cerint , e se va folosi repetat algoritmul lui Euclid pentru determinarea
celui mai mic divizor comun (cmmdc) al numerelor din fiecare s , ir.
Dac˘a s , irul are un singur element, cmmdc va fi chiar valoarea elementului, altfel determin˘am
cmmdc pentru primele dou˘a numere, apoi pentru rezultat s , i al treilea num˘ar, etc, pˆan˘a epuiz˘am
toate elementele s , irului.
Pentru cerint , a a doua, Mihai poate cˆas , tiga dac˘a poate ˆımp˘art , i elementele s , irului la cmmdc-ul
acestora (calculat la punctul 1). Prin urmare, dorim s˘a verific˘am, pentru fiecare s , ir, dac˘a
cmmdc-ul elementelor s , irului se poate descompune ˆıntr-un produs de factori mai mici sau egali
cu k. Pentru ca acest lucru s˘a fie adev˘arat, trebuie ca tot , i factorii primi al cmmdc-ului s˘a fie
mai mici sau egali cu k.
Observat , ie. Este suficient s˘a parcurgem valorile de la 1 la sqrt(cmmdc) pentru a c˘auta factorii
primi ai cmmdc-ului. Pentru fiecare i de la 1 la sqrt(cmmdc) vom verifica dac˘a i, respectiv
cmmdc/i sunt prime s , i, dac˘a da, vom testa dac˘a sunt mai mici sau egale cu k. Dac˘a vreunul
este mai mare sau egal cu k, r˘aspunsul va fi NO.
La final, dac˘a tot , i factorii primi au fost mai mici sau egali cu k, vom afis , a YES.
Problema 2 – spirala
Alex, elev ˆın clasa a IX-a la un liceu din Pites , ti, a primit de ziua lui un joc de la fratele s˘au
– student la Informatic˘a ˆın anul I, Universitatea din Pites , ti. Jocul este format dintr-o tabl˘a
2
2
p˘atratic˘a ˆımp˘art , it˘a ˆın n p˘atr˘at , ele, cˆate n pe fiecare linie, s , i din n jetoane pe care sunt scrise
numere naturale (cˆate un num˘ar pe fiecare jeton). Jocul const˘a ˆın as , ezarea aleatorie a jetoanelor
pe tabl˘a s , i, pentru o valoare natural˘a k, trebuie s˘a determin˘am primul subtablou de dimensiune
k care are proprietatea c˘a s , irul componentelor parcurse ˆın spiral˘a este o progresie aritmetic˘a
cresc˘atoare. Subtablourile de dimensiune k sunt parcurse ˆın ordinea cresc˘atoare a coordonatelor
colt , ului din stˆanga-sus. (i, j) < (p, q) dac˘a (i < p) sau (i = p s , i j < q).
Cerint , ˘a
Cunoscˆand n, k s , i o as , ezare a jetoanelor pe tabl˘a se cere s˘a determinat , i:
1. cel mai mare num˘ar din primul subtablou de dimensiune k;
2. coordonatele colt , ului din stˆanga-sus (linie coloan˘a) ale primului subtablou de dimensiune k
care are proprietatea c˘a s , irul componentelor parcurse ˆın spiral˘a este o progresie aritmetic˘a
cresc˘atoare.
Date de intrare
Fis , ierul de intrare spirala.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 dimensiunea n a tablei s , i num˘arul k, separate printr-un spat , iu.
Urmeaz˘a n linii cu cˆate n numere separate prin cˆate un spat , iu, ce reprezint˘a valorile de pe
jetoanele aflate pe tabla jocului.
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 spirala.out se va scrie un singur num˘ar natural reprezentˆand cel mai mare
num˘ar din primul subtablou de dimensiune k.
