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  săli numerotate de la  la  în sens trigonometric. Iniţial, toate  sălile sunt goale. Prima sală este numerotată cu  şi în ea intră câte  oameni în fiecare minut. Următoarele  săli au uşi de ieşire. Din sala vor ieşi în fiecare minut  oameni, dar numai dacă există cel puţin  oameni în sala respectivă. După ce intră oameni în sala  ş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  atunci el trece în sala , iar dacă este în sala  atunci trece în sala .
 
h2. Cerinţă
 
Să se scrie un program care pentru numere cunoscute şi sirul  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 expozitie.in conţine pe prima linie numerele  şi . Pe a doua linie vor exista  numere separate prin câte un spaţiu reprezentând elementele vectorului . Pe următoarele  linii vor fi descrise cele  î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 expozitie.out va conţine  linii. Pe aceste linii se vor găsi răspunsurile la cele  î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") ==