InfoAs Atlas

<- Go back View preview

Problema Tort

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

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

Examples

Default code

Summary

Editorial

_Descriere oferită de propunători._

_Propunător: prof. Marius Nicoli_

**Soluție pentru N ≤ 20.** O abordare prin care se generează toate modurile de a descompune în secvențe șirul dat obține punctele la aceste teste. De exemplu, se pot genera toate șirurile de `0` și de `1` care încep cu `1`, mai conțin încă un `1` cel puțin și care au lungimea `n`. Pozițiile pe care se află valoarea `1` sunt începuturile de secvențe ale unei descompuneri. Timpul de executare este de ordinul `2n * n`.

**Soluție pentru N ≤ 100, a** **1** **= … = a** **N** **= 1.** Toate elementele fiind egale cu `1`, odată ce fixăm prima secvență între indicii `1` și `i`, la soluție trebuie adunat numărul de divizori ai valorii `n - i` (suma numerelor de la poziția `i` până la poziția `n`). Timpul de executare este deci `n * sqrt(n)` dar se poate obține unul mai bun dacă ne gândim că este vorba de suma divizorilor pentru fiecare număr de la `1` la `n - 1`, iar aceste valori se pot calcula folosind ciurul lui Eratostene.

**Soluție pentru N ≤ 100.** Fixăm de asemenea prima secvență iar pentru restul descompunerii fixăm mai întâi suma comună pe care o dorim în restul secvențelor și apoi facem verificarea dacă descompunerea cu elementele fixate înainte este posibilă. Timpul de calcul este de ordinul `n2 * suma valorilor din șirul dat`.

**Soluție pentru N ≤ 100, a** **1** **\+ … + a** **N** **≤ 4000.** Odată ce fixăm prima secvență (până la poziția `i - 1`) ne dăm seama că suma comună din celelalte secvențe nu poate fi decât un divizor al valorii `Si` (`Si` = suma elementelor de la poziția `i` până la poziția `n`). Astfel este necesară verificarea doar pentru valorile acestor divizori. Avem timp de ordinul `n2` de la fixarea secvenței inițiale și de la verificare și se adaugă costul obținerii divizorilor lui `Si` (fie obținem divizorii la întâlnirea elementului curent cu timp de ordin `sqrt(Si)`, fie îi precalculăm folosind Ciurul lui Eratostene).

**Soluție pentru 100 de puncte.** Facem o parcurgere de la final și acumulăm la o sumă `s` valorile din șir pe măsură ce le întâlnim, marcând într-un vector de frecvență în dreptul sumelor obținute. Pe acest vector, pentru valori naturale `i`, începând cu `1`, verificăm cât putem merge plecând de la indicele `i` și avansând din `i` în `i` pe elemente marcate, fiecare pas făcut reprezentând de altfel o soluție. Este de fapt o simulare a algoritmului de la Ciurul lui Eratostene, aceasta fiind și cel care dă complexitatea în timp a unei soluții care se încadrează în timp pe toate testele.

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	3 KB	View
0-tort.in	/ 100	10 January 2025 21:26	50 B	View
0-tort.ok	/ 100	10 January 2025 21:26	3 B	View
1-tort.in	/ 100	10 January 2025 21:26	93 B	View
1-tort.ok	/ 100	10 January 2025 21:26	3 B	View
2-tort.in	/ 100	10 January 2025 21:26	99 B	View
2-tort.ok	/ 100	10 January 2025 21:26	3 B	View
3-tort.in	/ 100	10 January 2025 21:26	103 B	View
3-tort.ok	/ 100	10 January 2025 21:26	4 B	View
4-tort.in	/ 100	10 January 2025 21:26	153 B	View
4-tort.ok	/ 100	10 January 2025 21:26	4 B	View
5-tort.in	/ 100	10 January 2025 21:26	204 B	View
5-tort.ok	/ 100	10 January 2025 21:26	4 B	View
6-tort.in	/ 100	10 January 2025 21:26	296 B	View
6-tort.ok	/ 100	10 January 2025 21:26	4 B	View
7-tort.in	/ 100	10 January 2025 21:26	288 B	View
7-tort.ok	/ 100	10 January 2025 21:26	4 B	View
8-tort.in	/ 100	10 January 2025 21:26	371 B	View
8-tort.ok	/ 100	10 January 2025 21:26	4 B	View
9-tort.in	/ 100	10 January 2025 21:26	398 B	View
9-tort.ok	/ 100	10 January 2025 21:26	4 B	View
10-tort.in	/ 100	10 January 2025 21:26	420 B	View
10-tort.ok	/ 100	10 January 2025 21:26	4 B	View
11-tort.in	/ 100	10 January 2025 21:26	840 B	View
11-tort.ok	/ 100	10 January 2025 21:26	4 B	View
12-tort.in	/ 100	10 January 2025 21:26	1 KB	View
12-tort.ok	/ 100	10 January 2025 21:26	5 B	View
13-tort.in	/ 100	10 January 2025 21:26	1 KB	View
13-tort.ok	/ 100	10 January 2025 21:26	5 B	View
14-tort.in	/ 100	10 January 2025 21:26	1 KB	View
14-tort.ok	/ 100	10 January 2025 21:26	5 B	View
15-tort.in	/ 100	10 January 2025 21:26	1 KB	View
15-tort.ok	/ 100	10 January 2025 21:26	5 B	View
16-tort.in	/ 100	10 January 2025 21:26	1 KB	View
16-tort.ok	/ 100	10 January 2025 21:26	5 B	View
17-tort.in	/ 100	10 January 2025 21:26	1 KB	View
17-tort.ok	/ 100	10 January 2025 21:26	5 B	View
18-tort.in	/ 100	10 January 2025 21:26	275 KB	View
18-tort.ok	/ 100	10 January 2025 21:26	7 B	View
19-tort.in	/ 100	10 January 2025 21:26	262 KB	View
19-tort.ok	/ 100	10 January 2025 21:26	8 B	View
20-tort.in	/ 100	10 January 2025 21:26	306 KB	View
20-tort.ok	/ 100	10 January 2025 21:26	7 B	View
21-tort.in	/ 100	10 January 2025 21:26	303 KB	View
21-tort.ok	/ 100	10 January 2025 21:26	8 B	View
22-tort.in	/ 100	10 January 2025 21:26	371 KB	View
22-tort.ok	/ 100	10 January 2025 21:26	7 B	View
23-tort.in	/ 100	10 January 2025 21:26	316 KB	View
23-tort.ok	/ 100	10 January 2025 21:26	8 B	View
24-tort.in	/ 100	10 January 2025 21:26	390 KB	View
24-tort.ok	/ 100	10 January 2025 21:26	8 B	View
In total: 52 files 2 MB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Tort

Identification properties

Content properties

Technical properties

Delete all files