Prefixos i sufixos P96912


Statement
 

pdf   zip

html

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.

Public test cases

  • 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
    • Information
    Author
    Jordi Cortadella
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++