== include(page="template/taskheader" task_id="era") ==
!>problema/era?era1.png!
Braţul Robotic European (ERA) este un braţ robotizat format din mai multe segmente, ataşat Staţiei Spaţiale Internaţionale şi a fost dezvoltat pentru Agenţia Spaţială Europeană de o serie de companii spaţiale europene. ERA este format din $N$ segmente notate $S{~1~}, S{~2~}, ..., S{~N~}$, oricare două segmente consecutive fiind articulate, ceea ce permite aşezarea oricărui segment pe orizontală sau pe verticală. Segmentul iniţial $S{~1~}$ este fixat cu capătul liber în originea sistemului de axe $XOY$.
În funcţie de cum poziţionăm segmentele, capătul liber al ultimului segment $S{~N~}$ poate ajunge în diferite poziţii din plan.
De exemplu, pentru $N = 2$ şi $L{~1~} = 3$, $L{~2~} = 4$ pot fi atinse următoarele puncte de coordonate întregi din plan:
* Punctul 1 se atinge cu $S{~1~}$ orizontal dreapta şi $S{~2~}$ orizontal dreapta.
* Punctul 2 se atinge cu $S{~1~}$ vertical sus şi $S{~2~}$ orizontal dreapta.
* Punctul 3 se atinge cu $S{~1~}$ orizontal dreapta şi $S{~2~}$ vertical sus.
* Punctul 4 se atinge cu $S{~1~}$ vertical sus şi $S{~2~}$ vertical sus.
* Punctul 5 se atinge cu $S{~1~}$ orizontal stânga şi $S{~2~}$ orizontal dreapta.
* Punctul 6 se atinge cu $S{~1~}$ vertical jos şi $S{~2~}$ vertical sus.
!>problema/era?era2.png!
Analog se obţin şi celelalte puncte marcate pe figură. În total, pot fi atinse de capătul liber al ultimului segment, 16 puncte de coordonate întregi.
h2. Cerinţă
Scrieţi un program care, cunoscând numărul de segmente $N$ al ERA şi lungimile $L{~1~}, L{~2~}, ..., L{~N~}$ ale fiecărui segment, să determine numărul $P$ de puncte distincte cu ambele coordonate numere întregi în care poate ajunge capătul liber al ultimului segment $S{~N~}$.
Braţul Robotic European (ERA) este un braţ robotizat format din mai multe
segmente, ataşat Staţiei Spaţiale Internaţionale şi a fost dezvoltat pentru Agenţia
Spaţială Europeană de o serie de companii spaţiale europene. ERA este format !problema/era?era1.1.png!
din 푁 segmente notate 푆1, 푆2, . . . 푆푁 , oricare două segmente consecutive fiind
articulate, ceea ce permite aşezarea oricărui segment pe orizontală sau pe verticală.
Segmentul iniţial 푆1 este fixat cu capătul liber în originea sistemului de
axe XOY.
În funcţie de cum poziţionăm segmentele, capătul liber al ultimului segment 푆푁
poate ajunge în diferite poziţii din plan.
h2. Date de intrare
Fişierul de intrare $era.in$ conţine pe prima linie numărul natural $N$ şi pe a doua linie numerele naturale nenule $L{~1~}, L{~2~}, ..., L{~N~}$ separate prin câte un spaţiu.
Fişierul de intrare $era.in$ ...
h2. Date de ieşire
Fişierul de ieşire $era.out$ conţine o singură linie pe care este scris numărul $P$ al punctelor distincte de coordonate întregi care pot fi atinse de capătul liber al ultimului segment S{~N~}.
În fişierul de ieşire $era.out$ ...
h2. Restricţii şi precizări
h2. Restricţii
* $1 ≤ N ≤ 100 000$
* $1 ≤ L{~i~} ≤ 100$ pentru orice $1 ≤ i ≤ N$
* Segmentele braţului robotic au grosime neglijabilă şi se pot suprapune.
|_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $L{~1~} = L{~2~} = ... = L{~N~}$|
| $2$ | $20$ | $1 ≤ N ≤ 20$, $1 ≤ L{~i~} ≤ 50$ pentru orice $1 ≤ i ≤ N$|
| $3$ | $11$ | $21 ≤ N ≤ 100$ |
| $4$ | $24$ | $101 ≤ N ≤ 10 000$ |
| $5$ | $37$ | Fără restricţii suplimentare |
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. era.in |_. era.out |_. Explicaţii|
| 2
3 4
| 16
| Conform figurii de mai sus |
| 8
50 47 23 35 10 49 5 4
| 28224
| Numărul de puncte de coordonate întregi
accesibile de capătul liber al ERA este de
28224.
|
table(example). |_. era.in |_. era.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="era") ==
