Prefixos i sufixos P96912
Considereu un vector v de n nombres naturals. Trobeu el prefix més curt (però no buit) del vector tal que existeixi un sufix del vector amb la mateixa suma.
Per exemple, si v és [1, 2, 5, 6, 8, 9, 12, 4, 3], el prefix demanat és [1, 2], el qual suma el mateix que el sufix [3]. Com un altre exemple, si v és [3, 2, 3, 5, 2, 6, 1, 1, 1, 3, 1, 2, 4], el prefix és [3, 2, 3, 5], amb la mateixa suma que [1, 1, 1, 3, 1, 2, 4]. Com a últim exemple, per a [1, 2, 3, 4] el prefix és el vector sencer [1, 2, 3, 4].
Entrada
L’entrada consisteix en diversos casos, cadascun amb n, seguida dels n naturals de v, tots entre 0 i 104. Suposeu 1 ≤ n ≤ 105.
Sortida
Per a cada cas, escriviu la longitud del prefix més curt que compleix la propietat demanada. Fixeu-vos que sempre existeix alguna solució.
Pista
La solució esperada té cost linial.
Input
9 1 2 5 6 8 9 12 4 3 13 3 2 3 5 2 6 1 1 1 3 1 2 4 4 1 2 3 4 1 0 5 0 1000 2 3 1000
Output
2 4 4 1 2
- Author
- Jordi Cortadella
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++