Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | rell.in, rell.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Mihai-Alexandru Dușmanu | Teodor Plop | Adăugată de |
Teodor Plop
•
teodor94
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 1024 KB |
| Scorul tău | N/A | Dificultate |
   2.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Rell's Report
În mirificul ținut al Pădurii de Jad, eroul nostru Rell, are de înfruntat ambuscada neașteptată a maimuțelor. Orice maimuță are un număr de puncte de viață. Se consideră că o maimuță este înfrântă în momentul în care numărul punctelor ei de viață ajunge la 0.
Se știe că eroul nostru are la dispoziție N abilități pe care le poate folosi pentru a ataca o maimuță. Pentru fiecare abilitate i se cunoaște dauna pe care o produce, A[i] și numărul de secunde de care are nevoie abilitatea pentru a se regenera, T[i]. De asemenea, Rell poate folosi maxim o abilitate pe secundă!
De exemplu, dacă Rell atacă o maimuță care are numărul de puncte de viață X în secunda T cu abilitatea i, acea maimuță va rămâne cu max( X – A[i], 0 ) puncte de viață, iar eroul nostru își va mai putea folosi abilitatea i abia în secunda T + T[i].
Toata lumea știe că ratonii sunt niște creaturi foarte curioase din fire. De la această regulă nu face excepție nici ratonul nostru, pe nume Socks. Acesta îi pune lui Rell Q întrebări în felul următor:
- Care este timpul minim în care poți înfrânge o maimuță care are X puncte de viață?
Date de intrare
Fișierul de intrare rell.in conține pe prima linie numărul N. Pe următoarele N linii se află câte două numere naturale, A[i] și T[i], separate între ele printr-un spațiu. Pe următoarea linie se află numărul natural Q. Pe următoarele Q linii se află câte un număr X, reprezentând întrebarea lui Socks.
Date de ieșire
În fișierul de ieșire rell.out se vor gasi Q linii, fiecare linie i conținând un singur număr, reprezentând răspunsul la întrebarea cu numărul i, pusă de Socks.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ A[i], T[i] ≤ 1.000.000
- 1 ≤ Q ≤ 1.000
- 1 ≤ X ≤ 1.000.000
- Atenție! Rell poate folosi maxim o abilitate pe secundă.
Exemplu
| rell.in | rell.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
