Fişierul intrare/ieşire:perioada01.in, perioada01.outSursăAlgoritmiada 2015 Runda 1
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.9 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Perioada01

Se dau doua numere N si P. Se considera sirul de caractere de lungime N (indexat de la pozitia 1 la N), plin cu 0. Seful la bani stie ca a ales P pozitii distincte pe care le-a transformat din 0 in 1. Intrebarea lui este daca sirul nou format este periodic sau nu (un sir se numeste periodic daca se poate obtine prin concatenarea repetata a unui prefix de al sau, cu lungime strict mai mica decat lungimea sirului; Spre exemplu "101010" este periodic deoarece are perioada "10", dar "10011" nu este periodic). Daca este periodic, se va afisa lungimea perioadei minime a acestuia, altfel -1.

Date de intrare

Fişierul de intrare perioada01.in va contine pe prima linie 2 numere N si P. Pe urmatoarea linie vor fi P numere, reprezentand pozitiile distincte la care s-au efectuat schimbarile (din 0 in 1).

Date de ieşire

Fişierul de ieşire perioada01.out va contine un singur numar: -1 daca sirul nu este periodic si minLength daca sirul este periodic (unde minLength reprezinta lungimea perioadei minime)

Restricţii

  • 2 ≤ N ≤ 1.000.000.000
  • 1 ≤ P ≤ ≤ 1.000.000
  • Pentru 20% din teste N ≤ 100.000
  • Pentru alte 20% din teste N ≤ 10.000.000 si P ≤ 100
  • Pentru alte 20% din teste P ≤ 100.000
  • Pozitiile sunt date in ordine crescatoare
  • P ≤ N

Exemplu

perioada01.inperioada01.out
999999999 3
1 333333334 666666667
333333333
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?