Problemă de concurs certificată de InfoAs: Soluțiile tale trimise la această problemă sunt evaluate în exact același mediu ca și la concurs.
OJI 2021 · Clasa a IX-aVectori (tablouri unidimensionale)Vectori de frecvență și vectori caracteristici
Problema Tort
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 ai 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ță – 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 a1, …, aN, 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.0001 ≤ a1, …, aN ≤ 400.000a1 + … + aN ≤ 400.000
Pentru 12 puncte
1 ≤ N ≤ 20
Pentru alte 12 puncte
1 ≤ N ≤ 100,a1 = … = aN = 1
Pentru alte 20 de puncte
1 ≤ N ≤ 100
Pentru alte 28 de puncte
1 ≤ N ≤ 1000,a1 + … + aN ≤ 2000
Pentru alte 28 de puncte
- Fără alte restricții
Exemplu
5 1 1 2 1 1
6
Explicația exemplului
Î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]
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;