Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | temple.in, temple.out | Sursă | Infoarena Monthly 2014, Runda 8 |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Temple
Tassadar vrea să exploreze un templu Xel’Naga, dar pentru a putea intra, trebuie să introducă un cod secret. În urma unor calcule matematice, a făcut câteva observaţii cu ajutorul cărora poate descoperi codul secret.
Fie o constantă K şi un şir V de N numere întregi. Fiecare poziţie i din şir are asociat un cost Ci. Definim Nexti = max(i, min(j | i < j, Vi < Vj)), iar NextiP = NextNexti(P – 1).
Fie şirul S de N numere întregi, Si = min(Ci, CNexti, CNexti2, ..., CNextiK). Codul secret este chiar şirul S!
Tassadar a reuşit să pătrundă în templul Xel’Naga. Voi puteţi?
Date de intrare
Fişierul de intrare temple.in conţine pe prima linie două numere întregi N şi K cu semnificaţia din enunţ. Pe a doua linie se află N numere întregi Vi reprezentând şirul V. Linia următoare conţine N numere întregi Ci reprezentând costurile poziţiilor din şirul V.
Date de ieşire
În fişierul de ieşire temple.out veţi afişa pe prima linie N numere întregi Si reprezentând codul secret.
Restricţii
- 1 ≤ K ≤ N ≤ 105
- 1 ≤ Vi ≤ 109
- -1015 ≤ Ci ≤ 1015
Exemplu
| temple.in | temple.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
