problema/tort4

tort4

Aici este problema Mirunei

== include(page="template/taskheader" task_id="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.
 
h2. 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.
 
h2. 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.
 
h2. Date de ieşire
 
Singura linie a fişierului de ieşire $tort.out$ va conţine numărul cerut.
 
h2. 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.
 
h2. Exemple
 
table(example). |_. tort4.in |_. tort4.out |
| 5
1 1 2 1 1
| 6
|
 
h3. 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]$
 
== include(page="template/taskfooter" task_id="tort4") ==
 

public

task: tort4