Fişierul intrare/ieşire:complet.in, complet.outSursăLot Vaslui 2014 Seniori Baraj 6
AutorAdrian PanaeteAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Complet

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ă vi. Valorile din vârfuri se transformă începând cu un moment inţial T0=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.

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.

Date de intrare

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 (t1, p1), (t2, p2), (t3, p3). Întrebarea i (cu i=4..Q) va fi generată cu relaţiile:
- ti = 1 + (ti-3 * x + ti-2 * y + ti-1 * z) mod 1015
- pi = 1 + (pi-3 * x + pi-2 * y + pi-1 * z) mod N
- x, y, z sunt numere naturale nenule fixate de cel mult 3 cifre

Date de ieşire

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.

Restricţii

  • 2 ≤ N ≤ 100 000
  • Valorile initiale din noduri sunt numere naturale si mai mici sau egale cu 30 000
  • 1 ≤ pi ≤ N
  • 0 ≤ ti ≤ 1015 pentru fiecare intrebare
  • 3 ≤ Q ≤ 1 000 000

Exemplu

complet.incomplet.out
4 4
1 4 2 3
1 1 1 1 1 1 1 1 1
6
6
6
204

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?