Fişierul intrare/ieşire: | zalmoxis.in, zalmoxis.out | Sursă | BOI 2018 |
Autor | Tamio-Vesa Nakajima | Adăugată de | Tamio Vesa Nakajima •tamionv |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zalmoxis
Tanaka a devenit interesat de Mitologia Dacă (dacii au trăit în zona României înaintea romanilor). În această mitologie, Zalmoxis era zeul suprem, iar Pleistoros zeul războiului. În noua interpretare a mitologiei făcută de Tanaka, Zalmoxis are o nouă putere, ZalLovitura, şi îi plac ZalSecvenţele.
ZalLovitura este un atac care poate fi aplicat pe secvenţe non-negative de întregi. Atacul constă în alegerea unui întreg strict pozitiv x din secvenţă şi înlocuirea lui cu alte două valori x-1. De exemplu:
- {1} {0, 0}
- {1, 23, 3} {1, 22, 22, 3}
- Dar nu este cazul ca {1, 3} {2, 1, 2}, deoarece ordinea din secvenţă contează.
ZalSecvenţele – secvenţele care îi plac lui Zalmoxis – sunt următoarele:
- Secvenţa {30}.
- O secvenţă care poate fi obţinută prin aplicarea unei ZalLovituri altei ZalSecvenţe.
De exemplu, , {29, 29} şi {29, 28, 27, 27} sunt ZalSecvenţe, dar {28, 29, 28} nu este.
Pentru început, Zalmoxis crează o ZalSecvenţă de lungime N + K. După aceasta, unul dintre inamicii săi distruge K dintre valorile din această secvenţă, lăsând doar N valori. Fie notată această secvenţă cu S. Cu N, K si S date, introduceţi K valori în S astfel încăt să creaţi orice ZalSecvenţă de lungime N + K. Se garantează ca pentru orice test există solutie.
Date de intrare
Prima linie a fisierului de intrare zalmoxis.in conţine numerele întregi pozitive N si K.
A doua linie conţine N întregi ne-negativi, valorile lui S.
Date de ieşire
Prima linie a fisierului de iesire zalmoxis.out conţine numerele întregi nenegative ale ZalSecventei de lungime N + K
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ K ≤ 1.000.000
- 1 ≤ N + K ≤ 1.000.000
- Secvenţa din fişierul de intrare este un subşir al unei ZalSecvenţe de lungime N + K.
- Pentru teste in valoare de 30 de puncte, K = 1.
- Toate testele folosite nu sunt grupate.
Exemplu
zalmoxis.in | zalmoxis.out |
---|---|
5 1 29 27 25 25 28 | 29 27 25 25 26 28 |
1 5 29 | 29 28 27 26 25 25 |
Explicaţie
În primul exemplu, {29, 27, 25, 25, 26, 28} poate fi obţinută din {30} prin următoarele ZalLovituri:
{30} → {29, 29} → {29, 28, 28} → {29, 27, 27, 28} → {29, 27, 26, 26, 28} → {29, 27, 25, 25, 26, 28}
În al doilea exemplu, {29, 28, 27, 26, 25, 25} poate fi obţinută din {30} prin următoarele ZalLovituri:
{30} → {29, 29} → {29, 28, 28} → {29, 28, 27, 27} → {29, 28, 27, 26, 26} → {29, 28, 27, 26, 25, 25}