Page 116 - MATINF Nr.2

˘
116 PROBLEME DE INFORMATICA PENTRU CONCURSURI

˘
PROBLEME DE INFORMATICA PENTRU
CONCURSURI

Probleme propuse

Clasa a IX-a

I 16 (numere). Tic˘a s , i Ionic˘a sunt buni prieteni, pasionat , i de matematic˘a s , i de informatic˘a.
Aces , tia particip˘a la un concurs de propun˘atori de probleme pe echipe. Pentru a avea succes
Tic˘a vrea s˘a propun˘a o problem˘a cu s , iruri, iar Ionic˘a o problem˘a cu numere libere de p˘atrate.
Numerele libere de p˘atrate sunt cele care se pot scrie ca un produs de numere prime distincte.
ˆ
Au decis s˘a participe la concurs cu o problem˘a care foloses , te un s , ir s , i numere libere de p˘atrate. In
aceast˘a problem˘a se d˘a un s , ir de N numere naturale nenule. Cerint , a problemei este determinarea
num˘arului de numere libere de p˘atrate, notat cu A s , i lungimea maxim˘a a unei secvent , e din s , ir
format˘a numai din numere care nu sunt libere de p˘atrate, notat˘a cu B.
Cerint , ˘a

S , tiind N s , i termenii s , irului, s˘a se determine num˘arul de numere libere de p˘atrate s , i lungimea
maxim˘a a unei secvent , e din s , ir format˘a numai din numere care nu sunt libere de p˘atrate.

Date de intrare
Din fis , ierul numere.in se citesc: num˘arul cerint , ei, notat cu k, de pe prima linie, num˘arul
natural N de pe a doua linie s , i cei N termeni ai s , irului de pe linia urm˘atoare, separat , i prin cˆate
un spat , iu.
Date de ies , ire
ˆ
In fis , ierul numere.out se va scrie num˘arul A, dac˘a k = 1 s , i respectiv num˘arul B, dac˘a k = 2,
cu semnificat , ia din enunt , .

Restrict , ii s , i preciz˘ari
• 1 < N ≤ 25000, num˘ar natural
• Termenii s , irului sunt numere naturale nenule mai mici sau egale cu 1000000000
• Dac˘a toate numerele din s , ir sunt libere de p˘atrate perfecte, atunci B = 0
• Pentru prima cerint , ˘a se primes , te 50% din punctaj
• Secvent , a este o succesiune de elemente aflate pe pozit , ii consecutive
Exemple

numere.in numere.out Explicat , ie
1 3 k = 1 s , i deci afis , ˘am A.
4 Numerele libere de p˘atrate sunt 6, 7 s , i 14.
6 18 7 14
2 1 k = 2 s , i deci afis , ˘am B.
4 Secvent , a cu num˘ar maxim de numere care nu
6 18 7 14 sunt libere de p˘atrate este format˘a doar din 18.

Timp maxim de execut , ie: 0.1 secunde/test.
Memorie total˘a disponibil˘a 2 MB.
Doru Anastasiu Popescu, Pites , ti (Micul Gates, 2018)