== include(page="template/taskheader" task_id="complet") ==
Poveste şi cerinţă...
Se consideră un graf neorientat complet cu $N$ vârfuri etichetate de la $1$ la $N$. Asociem fiecărui vârf $i$ o valoare iniţială $v{~i~}$. Valorile din vârfuri se transformă începând cu un moment inţial $T{~0~}=0$ din secundă în secundă după următoarea regulă: valoarea într-un vârf $k$ la secunda $T+1$ este egală cu suma valorilor aflate în toate celelalte vârfuri la secunda $T$.
h2. Cerinta
Cunoscând $N$ – numărul de vârfuri ale grafului precum şi valorile iniţiale din vârfurile grafului, să se răspundă la $Q$ întrebări date perechi de forma $(t, p)$ cu semnificaţia: “Dacă după $t$ secunde se consideră valorile din vârfuri ordonate crescător, care este valoarea de pe poziţia $p$?”. Deoarece aceste valori pot fi foarte mari, acestea vor fi calculate modulo $40099$.
h2. Date de intrare
Fişierul de intrare $complet.in$ ...
Fişierul de intrare $complet.in$ conţine pe prima linie două numere naturale nenule separate printr-un spaţiu: $N$ şi $Q$. Pe a doua linie se găsesc $N$ numere naturale nenule separate prin câte un spaţiu, reprezentând valorile aflate iniţial în vârfurile grafului. Linia a treia conţine exact $9$ numere naturale separate prin câte un spaţiu $x y z t1 t2 t3 p1 p2 p3$ cu ajutorul cărora vor fi construite cele $Q$ întrebări. Primele trei întrebări sunt date de perechile $(t{~1~}, p{~1~}), (t{~2~}, p{~2~}), (t{~3~}, p{~3~})$. Întrebarea $i$ (cu $i=4..Q$) va fi generată cu relaţiile:
- $t{~i~} = 1 + (t{~i-3~} * x + t{~i-2~} * y + t{~i-1~} * z) mod 10^15^$
- $p{~i~} = 1 + (p{~i-3~} * x + p{~i-2~} * y + p{~i-1~} * z) mod N$
- $x, y, z$ sunt numere naturale nenule fixate de cel mult $3$ cifre
h2. Date de ieşire
În fişierul de ieşire $complet.out$ ...
Fişierului de ieşire $complet.out$ va conţine $Q$ linii, fiecare dintre acestea conţinând un singur număr reprezentând răspunsul la întrebarea corespunzătoare din fişierul de intrare, modulo $40099$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100 000$
* Valorile initiale din noduri sunt numere naturale si mai mici sau egale cu 30 000
* $1 ≤ p{~i~} ≤ N$
* $0 ≤ t{~i~} ≤ 10^15^$ pentru fiecare intrebare
* $3 ≤ Q ≤ 1 000 000$
h2. Exemplu
table(example). |_. complet.in |_. complet.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4
1 4 2 3
1 1 1 1 1 1 1 1 1
| 6
6
6
204
|
h3. Explicaţie
...
Întrebările vor fi:
$1 1$
$1 1$
$1 1$
$4 4$
În secunda $1$ valorile sunt: $9 6 8 7$
După sortare, pe prima poziţie este $6$.
În secunda $4$ valorile sunt: $201, 204, 202, 203$
După sortare, pe a patra poziţie este $204$.
== include(page="template/taskfooter" task_id="complet") ==
