Diferente pentru problema/euclid1 intre reviziile #1 si #7

Diferente intre titluri:

euclid1
Euclid1

Diferente intre continut:

== include(page="template/taskheader" task_id="euclid1") ==
Poveste şi cerinţă...
După ce aţi mâncat la restaurantul lui Deadpool şi aţi scăpat din Matrix, vi se cere acum să vă întoarceţi în lume antică, mai exact la momentul inventării celui mai mare divizor comun.
 
În minunatul oraş Alexandria domnea un rege vicios. Regatul său era format din $N$ oraşe aşezate în linie dreaptă şi numerotate de la $1$ la $N$, iar fiecare oraş trebuia să plătească taxe (oraşul $i$ trebuie să plătească $V{~i~}$ monezi iniţial).
 
Din când în când, regele dorea să crească anumite taxe sau să îl întrebe pe Euclid care este cel mai mare număr care divide toate taxele dintr-un interval de oraşe.
 
h2. Cerinţă
 
Fiind dat şirul iniţial $V$, unde $V{~i~}$ reprezintă numărul de monezi pe care oraşul $i$ trebuie să le plătească regelui. Vi se cere să aplicaţi $Q$ operaţii pe acest şir, operaţii care se pot împarţi în două categorii:
 
* $query(a, b)$ - vi se cere să îl ajutaţi pe Euclid să calculeze cel mai mare divizor comun al valorilor $V{~a~}$, $V{~a+1~}$, $V{~a+2~}$, ..., $V{~b~}$
* $update(a, b, k)$ - regele măreste taxele după cum urmează:
** $V{~a~} += k$
** $V{~a+1~} += 2 x k$
** $V{~a+2~} += 3 x k$
** ...
** $V{~b~} += (b - a + 1) x k$
h2. Date de intrare
Fişierul de intrare $euclid1.in$ ...
Fişierul de intrare $euclid1.in$ conţine pe prima linie două numere întregi $N$ şi $Q$, reprezentând numărul oraşelor, respectiv numărul întrebărilor regelui. A doua linie conţine N numere întregi, şirul $V$. Următoarele Q linii conţin o operaţie, fiecare descrisă după cum urmează:
 
* dacă operaţia este $query(a, b)$, atunci linia va conţine trei numere întregi: $0 a b$
* dacă operaţia este $update(a, b, k)$, atunci linia va conţine patru numere întregi: $1 a b k$
h2. Date de ieşire
În fişierul de ieşire $euclid1.out$ ...
Fişierul de ieşire $euclid1.out$ trebuie să conţină răspunsul pentru fiecare întrebare de tip query, în ordinea în care acestea sunt date, separând fiecare răspuns prin câte o linie nouă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$
* $1 ≤ a ≤ b ≤ N$ pentru toate operaţiile.
* $1 ≤ k ≤ 200.000.000$ pentru toate operaţiile de tip update.
* $1 ≤ V{~i~} ≤ 200.000.000 (∀) 1 ≤ i ≤ N$
* Pentru $20%$ dintre teste $N, Q ≤ 1.000$
* Pentru alte $40%$ dintre teste $N, Q ≤ 70.000$
h2. Exemplu
table(example). |_. euclid1.in |_. euclid1.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...
table(example). |_. euclid1.in |_. euclid1.out |_. Explicaţie |
| 8 3
2 8 12 24 66 33 21 7
0 2 4
1 1 4 2
0 2 4
|4
2
| Pentru prima operaţie: se calculeaza cmmdc(8, 12, 24) = 4
In urma celei de a doua operaţie, şirul devine: (4, 12, 18, 32, 66, 33, 21, 7)
A treia operaţie: cmmdc(12, 18, 32) = 2
|
== include(page="template/taskfooter" task_id="euclid1") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.