Fişierul intrare/ieşire:zalmoxis.in, zalmoxis.outSursăBOI 2018
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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}  \xrightarrow{ZalLovitura} {0, 0}
  • {1, 23, 3}  \xrightarrow{ZalLovitura} {1, 22, 22, 3}
  • Dar nu este cazul ca {1, 3}  \xrightarrow{ZalLovitura} {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.inzalmoxis.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}

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?