Kermit

Osnovne informacije

Omejitve
  • Čas: 12 s
  • Spomin: 256 MB
Avtor:
  • Tomaž Hočevar
  • UPM

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Žabec Kermit se je znašel na prvem izmed N lokvanjev, ki so enakomerno razporejeni v krogu in oštevilčeni s števili od 1 do N v smeri urinega kazalca. V mladosti se je naučil izvajati skoke točno določenih dolžin, sedaj pa ni več najbolj dojemljiv za učenje novih trikov. Trenutno je obrnjen proti lokvanju številka 2 in se ne more obrniti v nasprotno smer. Za vsako od možnih dolžin skokov poznaš tudi količino energije, ki jo žabec porabi za tak skok. Q izmed lokvanjev ima za Kermita prav posebno čustveno vrednost. Za vsakega izmed njih izračunaj, koliko energije bo Kermit porabil, da ga doseže, če izbere optimalno zaporedje skokov.

Vhodni podatki

Prva vrstica vsebuje števili N in M. Naslednjih M vrstic opisuje skoke, ki jih lahko izvede žabec. Vsak skok je opisan z dolžino skoka D_i in porabo energije E_i. Sledi število Q, v naslednji vrstici pa še seznam številk lokvanjev, ki jih želi žabec doseči.

Omejitve vhodnih podatkov

  • 3 \leq N \leq 10^6
  • 1 \leq M \leq 100
  • 1 \leq D_i \lt \min(N,1000)
  • 1 \leq E_i \leq 1000
  • 1 \leq Q \leq 10^4

Opomba: Sodniški ekipi pri danih omejitvah ni uspelo napisati dovolj hitre rešitve v pythonu. Svetujemo uporabo C/C++, pascala ali jave.

Izhodni podatki

Izpiši Q vrstic. V i-ti vrstici izpiši najmanjšo količino energije, ki jo žabec porabi, da iz lokvanja številka 1 priskače na lokvanj L_i. Če lokvanja ne more doseči, izpiši -1.

Primer

Vhod

12 3
2 2
8 1
4 10
6
3 8 5 7 11 1

Izhod

2
-1
2
4
3
0
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task