== include(page="template/taskheader" task_id="hamster") ==
Poveste şi cerinţă...
După atâţia ani de mâncat seminţe, Hamsterul Vlăduţ a decis să treacă la o dietă mai sănătoasă. El are o pistă de alergare ce constă într-un dreptunghi format prin alipirea a mai multor celule 1x1 cap la cap, startul şi finishul fiind cele două muchii care mărginesc pista. Acesta şi-a stabilit liniştit programul de alergare zilnică pe pistă - În fiecare dintre următoarele T zile el va alerga un număr ales de el de celule. Mai precis, în ziua cu numărul i, el va alerga un număr de d_i celule (Vlăduţ porneşte din marginea cea mai din stânga şi aleargă spre dreapta până ce drumul său acoperă complet d_i dale, după care se opreşte). Cârtiţoiul Bobo, vechiul său duşman din copilărie, află de planul lui Vlăduţ şi decide să-l încurce puţin. El va alege un număr de N celule distincte şi va săpa câte un şanţ destul de mare în centrul fiecărei celule alese. Cum Hamsterul Vlăduţ nu este tocmai în forma şi este la începutul dietei, alege să nu sară peste şanţuri, ci să le acopere cu mai multe plăci identice. În ziua numărul i, el are la dispoziţie doar plăci de dimensiune 1xD_i, dar în număr nelimitat.
După atâţia ani de mâncat seminţe, Hamsterul Vlăduţ a decis să treacă la o dietă mai sănătoasă. El are o pistă de alergare ce constă într-un dreptunghi format prin alipirea mai multor celule <tex>1 \times 1</tex> cap la cap, startul şi finishul fiind cele două muchii care mărginesc pista (stânga şi respectiv dreapta). El îşi propune să alerge în fiecare zi dintre următoarele <tex>Q</tex> zile. Cârtiţoiul Bobo, vechiul său duşman din copilărie, află de planul lui Vlăduţ şi decide să-l încurce puţin. El va alege un număr de <tex>N</tex> celule distincte ale pistei şi va săpa câte un şanţ exact după fiecăre celulă aleasă (dacă celula este <tex>i</tex>, el va crea un şanţ ce va separa celulele <tex>i</tex> şi <tex>i+1</tex>). Vlăduţ, văzând ce i-a făcut cârtiţoiul, se decide ca în fiecare zi să treacă peste primele <tex>K_i</tex> gropi (de la stânga spre dreapta), unde <tex>i</tex> este numărul zilei curente, iar <tex>K_i</tex> este un număr natural nenul ales de el. În plus, pentru că este la început şi îi este lene să sară peste gropi, el se gândeşte să împrumute de la vecinul său nişte plăci, cu care să acopere toate gropile din calea lui. Vecinul său îi poate împrumuta în ziua <tex>i</tex> un număr nelimitat de plăci <tex>1 \times D_i</tex>, însă cu condiţia de a le returna până seara.
Hamsterul Vlăduţ are nevoie de ajutorul vostru în a-şi realiza planul şi vă cere să aflaţi pentru fiecare zi dintre cele T ale dietei sale, care este numărul optim (minim) de plăci pe care trebuie să le folosească pentru a acoperi complet găurile pe care le are de parcurs.
Hamsterul Vlăduţ are nevoie de ajutorul vostru pentru a-şi realiza planul şi vă cere să aflaţi pentru fiecare zi dintre cele <tex>Q</tex> ale dietei sale, care este numărul optim (minim) de plăci pe care trebuie să le folosească pentru a acoperi complet găurile pe care le are de parcurs (o placă nu are voie să acopere o celulă doar parţial, iar o gaură se consideră acoperită dacă se află oriunde în interiorul plăcii, sau pe capete, exact ca la un interval închis).
!>problema/hamster?poza.jpg!
h2. Date de intrare
Fişierul de intrare $hamster.in$ conţine pe prima linie două numere naturale nenule, separate printr-un spaţiu, ce reprezintă în ordine numerele T şi N din enunţ. Pe următoarea linie se găsesc N numere naturale nenule separate două câte două alăturate printr-un spaţiu, reprezentând indicii celulelor în care Bobo sapă un şanţ. Fişierul mai conţine încă T linii, pe linia 2+j găsindu-se două numere naturale nenule separate printr-un spaţiu, reprezentând în ordine d_i şi D_i.
Fişierul de intrare $hamster.in$ conţine pe prima linie două numere naturale nenule, separate printr-un spaţiu, ce reprezintă în ordine numerele <tex>N</tex> şi <tex>Q</tex> din enunţ. Pe următoarea linie se găsesc <tex>N</tex> numere naturale nenule separate două câte două alăturate printr-un spaţiu, reprezentând indicii celulelor după care Bobo sapă un şanţ, în ordine crescătoare. Fişierul mai conţine încă <tex>Q</tex> linii, pe linia <tex>2+j</tex> găsindu-se două numere naturale nenule separate printr-un spaţiu, reprezentând în ordine <tex>K_i</tex> şi <tex>D_i</tex>.
h2. Date de ieşire
În fişierul de ieşire $hamster.out$ trebuie să se găsească o singură linie, aceasta conţinând T numere naturale separate fiecare două alăturate prin spaţiu, reprezentând în ordine numărul minim necesar de dale pentru fiecare zi a dietei.
În fişierul de ieşire $hamster.out$ trebuie să se găsească <tex>Q</tex> linii, fiecare conţinând câte un număr natural. Pe linia <tex>i</tex> se va găsi numărul minim necesar de plăci pentru ziua <tex>i</tex> a dietei.
h2. Restricţii
* $1 ≤ N ≤ Fa tu asta$
$1 ≤ T ≤ Fa tu asta$
$1 ≤ lungimea pistei ≤ Fa tu asta$
$1 ≤ D_i ≤ d_i ≤ Fa tu asta$
Se garantează că datele din fişierul de intrare sunt corecte (indicii gropilor nu vor depăşi lungimea maximă a pistei, D_i urile asemenea).
* **Subtask 1 (20 puncte)**: 1 ≤ <tex> N , Q </tex> ≤ 2000 şi 0 ≤ <tex> X_i </tex> ≤ 10^9^ (Feedback testul $4$)
* **Subtask 2 (30 puncte)**: 1 ≤ <tex> N </tex> ≤ 1000, 1 ≤ <tex> Q </tex> ≤ 3 * 10^5^, 0 ≤ <tex> X_i </tex> ≤ 10^9^ şi K = N (Feedback testele $7$ si $10$)
* **Subtask 3 (30 puncte)**: 1 ≤ <tex> N </tex> ≤ 1000, 1 ≤ <tex> Q </tex> ≤ 3 * 10^5^ şi 0 ≤ <tex> X_i </tex> ≤ 10^9^ (Feedback testul $16$)
* **Subtask 4 (20 puncte)**: 1 ≤ <tex> N </tex> ≤ 3000, 1 ≤ <tex> Q </tex> ≤ 3 * 10^5^ şi 0 ≤ <tex> X_i </tex> ≤ 10^15^ (Feedback testul $20$)
* În toate subtaskurile 2 ≤ <tex> K_i </tex> ≤ N si 1 ≤ <tex> D_i </tex>
* S-a notat cu <tex> X_i </tex> coordonata celei de a i-a gropi.
* Se garantează că datele din fişierul de intrare sunt corecte (indicii gropilor nu vor depăşi lungimea maximă a pistei, <tex>D_i</tex>-urile asemenea).
* Se garantează că oricare două poziţii diferite ale unor gropi au coordonate diferite.
* Indicii gropilor sunt deja ordonaţi crescători
* *ATENŢIE! Se recomandă parsarea fişierului de intrare $hamster.in$ pentru obţinerea scorului maxim. Puteţi folosi codul de pe siteul 'acesta':http://www.infoarena.ro/parsare-fisier-intrare (atât pentru utilizatorii de C++ şi sintaxă similară cu $fstream, cât şi pentru iubitorii de C pur$)*
h2. Exemplu
table(example). |_. hamster.in |_. hamster.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5 6
2 4 5 7 9
3 2
3 1
3 5
5 1
5 2
4 3
| 2
2
1
4
3
2 |
| 32 28
3 6 9 11 14 17 20 22 25 28 30 32 34 37 40 43 45 48 50 52 54 57 60 62 64 66 69 71 74 76 79 82
27 11
24 8
29 14
26 8
31 11
25 9
25 10
29 14
29 14
26 10
22 15
30 10
29 14
25 8
21 8
29 12
25 10
21 13
30 10
21 9
24 14
27 8
29 13
30 11
25 14
26 13
26 14
25 10
| 6
7
5
7
6
6
6
5
5
6
4
7
5
7
6
6
6
4
7
5
4
7
5
6
4
5
4
6
|
h3. Explicaţie
...
Primul exemplu este cel din poza.
== include(page="template/taskfooter" task_id="hamster") ==
== include(page="template/taskfooter" task_id="hamster") ==
