Fişierul intrare/ieşire:subsecventa.in, subsecventa.outSursăOlimpiada locala 2015, Clasa a 7-a
AutorAutor NecunoscutAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test1 secLimită de memorie3072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Subsecvenţa (clasa a 7-a)

Andrei este un elev extrem de silitor la şcoală, în special la matematică şi la informatică. Andrei a gasit intr-o carte următoarea afirmaţie: “Fiind dată o secvenţă de n numere naturale, există cel puţin o subsecvenţă (elemente consecutive în secvenţa dată) pentru care suma elementelor este divizibilă cu n”. Problema aceasta l-a pus pe ganduri şi a încercat să o demonstreze matematic, dar să gasească şi un algoritm de rezolvare.

Exemplu: dacă n=7 şi secvenţa de numere naturale (2,3,5,4,2,1,1) atunci subsecvenţele (2,3,5,4), (3,5,4,2), (4,2,1) au suma elementelor divizilă cu 7.

Cerinţă

Scrieţi un program care citeşte n numere naturale (x1,x2....xn). Ştiind ca există cel puţin o subsecvenţă (xi,xi+1....xj) pentru care s=(xi,xi+1....xj) este divizibilă cu n, să se afişeze indicele de inceput i şi respectiv indicele de sfârşit j al acelei subsecvenţe pentru care j este maxim.

Date de intrare

Fişierul de intrare subsecventa.in conţine pe prima linie numărul natural n, pe a doua linie cele n numere naturale.

Date de ieşire

Fişierul de ieşire subsecventa.out conţine pe prima linie două numere naturale separate printr-un spaţiu: i indicele de început şi respectiv j indicele de sfârşit al subsecvenţei din şirul dat pentru care suma elementelor este divizibilă cu n( j este maxim).

Restricţii

  • Pentru toate testele există o soluţie unică (în condiţiile problemei);
  • Pentru toate testele 2 ≤ n ≤ 10 000 iar 0 ≤ xi ≤ 1 000 ( 1 ≤ in ).

Exemplu

subsecventa.insubsecventa.outExplicaţii
5
1 1 1 5 1
4 4
Subsecvenţa are indicii cuprinşi între 4 şi 4.
10
1 1 1 1 2 2 2 2 2 3
5 9
Subsecvenţa are indicii cuprinşi între 5 şi 9
(suma 2+2+2+2+2 este divizibila cu 10, indicele 9 este maxim)
Trebuie sa te autentifici pentru a trimite solutii. Click aici