expozitie2

Expozitie2

== include(page="template/taskheader" task_id="expozitie2") ==

Poveste şi cerinţă...

O expoziţie de pictură este organizată într-o clădire circulară formată din $N + 1$ săli numerotate de la $0$ la $N$ în sens trigonometric. Iniţial, toate sălile sunt goale. Prima sală este numerotată cu $0$ şi în ea intră câte $Y$ oameni în fiecare minut. Următoarele $N$ săli au uşi de ieşire. Din sala $i, 1 ≤ i ≤ N$ vor ieşi în fiecare minut $x[i]$ oameni, dar numai dacă există cel puţin $x[i]$ oameni în sala respectivă. După ce intră oameni în sala $0$ şi pleacă eventual oameni din celelalte săli, în acelaşi minut, toţi cei rămaşi în expoziţie trec în sala următoare. Mai precis, dacă un om se află în sala $i ≤ N - 1$ atunci el trece în sala $i + 1$, iar dacă este în sala $N$ atunci trece în sala $0$.
 
h2. Cerinţă
 
Să se scrie un program care pentru numere $N, Q, y$ cunoscute şi sirul $x[i], 1 ≤ i ≤ N$ cunoscut, răspunde la  întrebări de forma : „Câţi oameni sunt după $t$ minute în sala $s$?”.

h2. Date de intrare

Fişierul de intrare $expozitie2.in$ ...

Fişierul de intrare $expozitie2.in$ conţine pe prima linie numerele $N$, $Q$ şi $y$. Pe a doua linie vor exista $N$ numere separate prin câte un spaţiu reprezentând elementele vectorului $x[]$. Pe următoarele $Q$ linii vor fi descrise cele $Q$ întrebări şi vor conţine câte două numere $t$ şi $s$ separate prin spaţiu reprezentând un număr de minute şi un număr de sală corespunzător unei întrebări.

h2. Date de ieşire

În fişierul de ieşire $expozitie2.out$ ...

Fişierul de ieşire $expozitie2.out$ va conţine $Q$ linii. Pe aceste linii se vor găsi răspunsurile la cele $Q$ întrebări în ordinea în care acestea apar în fişierul de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000;$
* $1 ≤ Q ≤ 1.000.000;$
* $1≤ y ≤ 1000;$
* $1≤ x[i] ≤ 100$ pentru fiecare $i$ cu $1 ≤ i ≤ N;$
* $0 ≤ s ≤ N$ pentru fiecare întrebare;
* $1≤ t ≤ 1.000.000.000$ pentru fiecare întrebare;

h2. Exemplu

table(example). |_. expozitie2.in |_. expozitie2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. expozitie2.in |_. expozitie2.out |_. Explicatie |
| 3 5 4
3 2 2
1 2
4 1
6 2
5 1
4 0
| 0
4
2
5
1
|Începând cu minutul 1 distribuţiile în cele 4 săli va fi următoarea:
0 4 0 0
0 4 1 0
0 4 1 1
1 4 1 1
1 5 1 1
1 5 2 1...

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="expozitie2") ==