Fişierul intrare/ieşire:	tort4.in, tort4.out	Sursă	OJSEPI 2021, clasa a 10-a
Autor	Marius Nicoli	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.15 sec	Limită de memorie	64000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tort4

Alexandra, prinţesa Regatului Visurilor a primit un tort şi vrea să îl împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din N bucăţi, iar a i-a bucată are a[i] cireşe. Alexandra va împărţi tortul în mai multe secvenţe continue de bucăţi, astfel încât fiecare bucată este inclusă în exact o secvenţă, şi fiecare secvenţă conţine cel puţin o bucată de tort. Prima secvenţa -- cea care conţine prima bucată -- o va mânca în noaptea de înaintea petrecerii, iar restul bucăţilor le va da celorlalţi prieteni invitaţi. Pentru a nu îi supăra, Alexandra vrea ca fiecare secvenţă dată unui prieten să conţină la fel de multe cireşe ca oricare altă secvenţă dată unui prieten (dar nu neapărat la fel de multe cireşe ca aceea mâncată de ea înaintea petrecerii). Alexandra trebuie să invite cel puţin un prieten la petrecere.

Cerinţă

Dându-se N şi şirul a, să se afle numărul de moduri în care Alexandra ar putea să împartă tortul în secvenţe continue, astfel încât să se respecte condiţiile din enunţ. Două moduri de a împărţi tortul se consideră a fi distincte dacă şi numai dacă există în unul o secvenţă care nu există în celălalt (dacă am reprezenta un mod de împărţire în secvenţe prin intermediul şirului crescător al indicilor de început pentru fiecare secvenţă din acea împărţire, două moduri de împărţire sunt distincte dacă şirurile de indici asociate lor sunt diferite).

Formal, dându-se un şir de numere, se vrea să aflăm numărul de moduri de a împărţi şirul în cel puţin două subsecvenţe, astfel încât sumele elementelor tuturor subsecvenţelor să fie egale, prima putând să aibă suma elementelor diferită de a celorlalte.

Date de intrare

Prima linie a fişierului de intrare tort.in conţine numărul N. A doua linie conţine valorile a[1], ..., a[N], separate prin spaţii.

Date de ieşire

Singura linie a fişierului de ieşire tort.out va conţine numărul cerut.

Restricţii şi precizări

• 1 ≤ N ≤ 200.000
• 1 ≤ a[1], ..., a[N] ≤ 400.000
• a[1] + ... + a[N] ≤ 400.000
• Pentru 12 puncte, 1 ≤ N ≤ 20.
• Pentru alte 12 puncte 1 ≤ N ≤ 100, a[1] = ... = a[N] = 1.
• Pentru alte 20 de puncte 1 ≤ N ≤ 100.
• Pentru alte 28 de puncte 1 ≤ N ≤ 1000, a[1] + ... + a[N] ≤ 2000
• Atenţie! Este posibil ca punctajul să difere faţă de cel luat în concurs.

Exemple

Explicaţie

Împărţirile valide sunt:

• [1], [1, 2, 1, 1]
• [1, 1], [2, 1, 1]
• [1, 1], [2], [1, 1]
• [1, 1, 2], [1, 1]
• [1, 1, 2], [1], [1]
• [1, 1, 2, 1], [1]

Cum se trimit solutii?