Fișierul intrare/ieșire	subsecventa.in, subsecventa.out	Sursă	Olimpiada locala 2015, Clasa a 7-a
Autor	autor necunoscut	Adăugată de	Marcela • Marcela
Timp de execuție pe test	1 sec	Limită de memorie	3072 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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 (x₁,x₂....x_n). Știind ca există cel puțin o subsecvență (x_i,x_i+1....x_j) pentru care s=(x_i,x_i+1....x_j) 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 ≤ x_i ≤ 1 000 ( 1 ≤ i ≤ n ).

Exemplu