Fişierul intrare/ieşire:spargere.in, spargere.outSursăONIS 2014, Runda 3
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.4 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/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.inspargere.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content