| Fişierul intrare/ieşire: | spargere.in, spargere.out | Sursă | ONIS 2014, Runda 3 |
| Autor | Teodor Plop | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Spargere
Georgică a terminat cu progresiile aritmetice şi si-a găsit o nouă ocupaţie: s-a decis să devină un spărgător profesionist. Primul pas în această carieră este spargerea seifurilor băncii Georgelonia. Banca are N seifuri, iar fiecare dintre acestea conţine o sumă infinită de bani. Pentru a nu declanşa alarma, Georgică trebuie să respecte următoarele reguli:
- Toate seifurile sunt deschise în secunda 0.
- Din fiecare seif i se poate lua o sumă de bani egală cu b[i].
- Fiecare seif i se va închide în momentul în care suma de bani este luată din el. Acesta se va deschide din nou peste exact t[i] secunde.
- Georgică poate lua bani din oricâte seifuri doreşte într-o secundă, condiţia fiind ca acestea să fie deschise.
De exemplu, dacă Georgică ia bani din seiful i la secunda T, acesta se va închide, urmând să se deschidă în secunda T + t[i].
Pentru a se asigura că este un spărgător bun, Georgică trebuie să răspundă la Q întrebări de tipul:
- Care este timpul minim în care poţi obţine o sumă de bani mai mare sau egală decât X?
Ajutaţi-l pe Georgică să devină un spărgător profesionist, răspunzând la întrebări!
Date de intrare
Fişierul de intrare spargere.in conţine pe prima linie numărul N. Pe următoarele N linii, se găsesc două numere naturale b[i] şi t[i], având semnificaţia din enunţ. Pe linia următoare, se găseşte numărul natural Q, iar pe urmatoarele Q linii se găseşte câte un număr X, reprezentând o întrebare pusă lui Georgică.
Date de ieşire
În fişierul de ieşire spargere.out se vor găsi Q linii, fiecare linie i conţinând un singur număr, reprezentând răspunsul la întrebarea i.
Restricţii
- 1 ≤ N ≤ 100
- 1 ≤ b[i], t[i] ≤ 1.000
- 1 ≤ Q ≤ 1.000
- 1 ≤ X ≤ 1.000.000.000
- Numerotarea secundelor se face începând cu secunda 0.
Exemplu
| spargere.in | spargere.out |
|---|---|
| 2 2 1 3 2 2 1 11 | 0 2 |
Explicaţie
În secunda 0, se vor lua bani din ambele seifuri. În total, vom avea 5 bani. Primul seif se va deschide din nou în secunda 1, iar cel de-al doilea în secunda 2. În secunda 1, vom lua din nou bani din primul seif. În total, vom avea 7 bani. Acesta se va deschide din nou în secunda 2. În secunda 2, vom lua bani din ambele seifuri. În total, vom avea 12 bani. Deci, în două secunde, avem cel puţin 11 bani.
