== include(page="template/taskheader" task_id="zudt") ==
Poveste și cerință...
Se consideră un număr natural [*N*] și un șir $[*A*]=([*a[~1~]*], [*a[~2~]*], [*a[~3~]*], ...,[*a[~N~]*])$ format din [*N*] numere naturale nenule. Definim [*S(i,j)*] ca fiind egal cu suma [*a[~i~]*]+[*a[~i+1~]*]+[*a[~i+2~]*]+ ... +[*a[~j~]*], unde 1 ≤ [*i*] ≤ [*j*] ≤ [*N*].
h2. Date de intrare
Fișierul de intrare $zudt.in$ ...
h2. Date de ieșire
h2. Cerințe
În fișierul de ieșire $zudt.out$ ...
Se cunosc numărul [*N*] și șirul A. Scrieți un program care să determine răspunsurile pentru următoarele trei întrebări:
h2. Restricții
# Există o poziție [*i*] (1 ≤ *i* < [*N*]) cu proprietatea că [*S(1,i)*]=[*S(i+1,N)*]?
# Există o poziție *i* (1 < i < [*N*]) cu proprietatea că [*S(1,i-1)*]=[*S(i+1,N)*]?
# Există două poziții *i* și *j* (1 < *i* și [*i*]+1 < *j* < [*N*]) cu proprietatea că [*S(1,i-1)*]=[*S(i+1,j-1)=S(j+1,N)*]?
* $... ≤ ... ≤ ...$
h2. Date de intrare
h2. Exemplu
Fișierul de intrare $zudt.in$ conține:
* pe prima linie, un număr natural [*C*] (1, 2 sau 3) reprezentând cerința care trebuie rezolvată;
* pe a doua linie, numărul natural [*N*] cu semnificația din enunț;
* pe a treia linie, [*N*] numere naturale nenule, separate prin câte un spațiu, reprezentând elementele șirului [*A*].
table(example).
|_. zudt.in |_. zudt.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Date de ieșire
h3. Explicație
Fișierul de ieșire $zudt.out$ conține pe prima linie răspunsul determinat pentru cerința [*C*]:
* Pentru [*C*]=1, prima linie conține un număr natural reprezentând răspunsul la prima intrebare. Dacă există o astfel de poziție *i* astfel încât [*S(1,i)=S(i+1,N)*], atunci răspunsul este numărul *i*. Dacă nu există, atunci răspunsul este numărul 0.
* Pentru [*C*]=2, prima linie conține un număr natural reprezentând răspunsul la a doua intrebare. Dacă există o astfel de poziție *i* astfel încât [*S(1,i-1)*]=[*S(i+1,N)*], atunci răspunsul este numărul *i*. Dacă nu există, atunci răspunsul este numărul 0.
* Pentru [*C*]=3, prima linie conține două numere naturale, separate printr-un singur spațiu, reprezentând răspunsul la a treia intrebare. Dacă există două poziții distincte *i* și *j* astfel încât [*S(1,i-1)*]=[*S(i+1,j-1)*]=[*S(j+1,N)*], atunci răspunsul este format din numărul *i* și numărul [*j*], în această ordine. Dacă nu există, atunci răspunsul este numărul 0.
h2. Restricții și precizări
* [*C*] ∈ {1, 2, 3}
* 5 ≤ [*N*] ≤ 200 000
* 1 ≤ a[~i~] ≤ 1000, [*i*]=1,2,...,[*N*]
* [*S(i,i)*]=a[~i~], i=1,2,...,[*N*]
table(){width:auto; border:none; outline:none; border-collapse:collapse}.
|_. # |_. Punctaj |_. Restricții |
| 1 | 60 | [*C*] = 1, [*N*] ≤ 1000 |
| 2 | 20 | [*C*] = 2, [*N*] ≤ 200 000 |
| 3 | 20 | [*C*] = 3, [*N*] ≤ 200 000 |
h2. Exemple
table(example).
|_. zudt.in |_. zudt.out |_. Explicații |
| 1
9
2 3 1 4 2 4 4 5 15
| 7
| i = 7
S(1,7)=20 și S(8,9)=20
|
| 1
5
2 3 1 4 6
| 0
| Nu există o poziție i cu proprietatea cerută.
S(1,1)=2, S(2,5)=14, 2 ≠ 14
S(1,2)=3, S(3,5)=13, 3 ≠ 13
S(1,3)=6, S(4,5)=10, 6 ≠ 10
S(1,4)=10, S(5,5)=6, 10 ≠ 5
|
| 2
5
2 3 1 4 2
| 0
| Nu există o poziție i cu proprietatea cerută.
i=2, S(1,1)=2, S(3,5)=7, 2 ≠ 7
i=3, S(1,2)=5, S(4,5)=6, 5 ≠ 6
i=4, S(1,3)=6, S(5,5)=2, 6 ≠ 2
|
| 2
9
2 3 1 4 202 7 1 1 1
| 5
| i=5
S(1,4)=10 și S(6,9)=10
|
| 3
9
2 3 1 8 6 7 2 2 2
| 4 6
| i=4 și j=6
S(1,3)=6, S(5,5)=6 și S(7,9)=6
|
...
== include(page="template/taskfooter" task_id="zudt") ==
