Pentru a putea rula codul, te rugăm să te autentifici.

Autentifică-te
main.cpp

Dificilă · 8

Memorie: 64 MB / 8 MB

Timp: 0.2 secunde

I/O: Fișiere

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.000
  • 1 ≤ a1, …, aN ≤ 400.000
  • a1 + … + 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

tort.in

5
1 1 2 1 1

tort.out

6

Explicație

Împărțirile valide sunt:

  1. [1], [1, 2, 1, 1]
  2. [1, 1], [2, 1, 1]
  3. [1, 1], [2], [1, 1]
  4. [1, 1, 2], [1, 1]
  5. [1, 1, 2], [1], [1]
  6. [1, 1, 2, 1], [1]
ID #107 Autor OJI 2021
Set Olimpiada Județeană de Informatică 2021, clasa a X-a Adăugată de Alexis Alexis lexington
Capitol Clasa a IX-a/Vectori (tablouri unidimensionale)/Vectori de frecvență și vectori caracteristici
Licență

Problema aceasta a fost publicată sub licența CC BY-SA 4.0. Indicațiile sunt publicate sub licența CC BY-SA 4.0, iar rezolvarea sub licența CC BY-SA 4.0. Licența InfoAs Standard License nu permite copierea sau modificarea fără acordul scris al autorilor. Platforma și toate funcționalitățile ei rămân în continuare proprietatea intelectuală Aspire Education Labs SRL. © 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

Lorem:

Pentru a vizualiza indicațiile problemei, te rugăm să te autentifici.

Indicații oficiale de rezolvare a problemei

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

#include <bits/stdc++.h>

    using namespace std;

    int main() {
        int n;
        cin >> n;
        cout << n * n << endl;
        return 0;
    }

Lorem:

Subtitle

Lorem ipsum, dolor sit amet consectetur adipisicing elit. Aperiam rem vel architecto dolore, nulla laboriosam atque laudantium sint commodi in molestiae excepturi dicta inventore eum, quos porro illum ratione ea! Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a? Nisi nostrum quod delectus corporis?

Lorem ipsum dolor sit amet consectetur adipisicing elit Lorem ipsum dolor sit amet consectetur adipisicing elit. Dolorum possimus dolores, molestiae sunt repellendus voluptate qui asperiores maiores cumque, quidem nihil facere distinctio! Odit, a?

Lorem:

Pentru a vizualiza rezolvarea problemei, te rugăm să te autentifici.

Soluții trimise la problema Tort

Soluții trimise 23
Soluții de 100 de puncte 6
Soluții de luna aceasta La fel de multe ca luna trecută. 0 +0
Rata de succes Rata dintre numărul de persoane care au obținut 100 de puncte și numărul total de persoane care au încercat problema. 54.55%

Autentifică-te pentru a vedea soluțiile tale.

Autentifică-te
  • Toate soluțiile tale le găsești aici. Găsești toate detaliile evaluării mai târziu, precum punctaje și sfaturi primite.
  • Poți să editezi soluțiile tale și să le retrimiți. Reia mai târziu de unde ai rămas, pentru că poți modifica soluții și să le reevaluezi.
  • Profesorii pot să vadă soluțiile tale și să îți trimită sugestii. Astfel, îți este mai ușor să înveți informatica, primind sfaturi bune chiar de la școală.

Ultimele soluții trimise 23

100 10000 100 10000 1000
1000000 100 100 100 10
10 10000 100 10000 10000
1000000 100000 10 100000 10
10 10000000 100 100000 10000
1000000 10000 1000 100 100000
10 10 100000 10000 10000
10 1000000 100 1000000 100000
10000 1000000 10000 100000 100000
1000 10 100000 100000 100000
Tabelul se actualizează în timp real. ?? / ??

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te