Fişierul intrare/ieşire:sir42.in, sir42.outSursăFMI No Stress 8
AutorLucian BicsiAdăugată defminostress2018Fmi no stress 2018 fminostress2018
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sir42

Este bine ştiut că cheia succesului în informatică este un şir binar (format din cifrele 0 şi 1) C de lungime N. Bineînţeles, datorită faptului că este foarte preţioasă, nu este ştiută de oricine. Totuşi, prietenii tăi au decis să te ajute să o aflii. Nu ţi-au oferit direct răspunsul (asta ar fi fost prea uşor - haha), însă ţi-au dat un număr K ≤ N şi un şir ajutător R, definit astfel: R(i) este cea mai din stânga poziţie j pentru care C(i) + ... + C(j) = K. Dacă pentru o poziţie i un asemenea j nu există, atunci R(i) = -1.

Cerinţă

Dându-se informaţiile date de prietenii tăi, află care este cheia succesului în informatică!

Date de intrare

Fişierul de intrare sir42.in va conţine pe prima linie numerele întregi N şi K, iar pe a doua linie N numere întregi, reprezentând şirul R.

Date de ieşire

În fişierul de ieşire sir42.out se va afişa un şir binar de exact N caractere, reprezentând soluţia problemei.

Restricţii

  • 1 ≤ K ≤ N ≤ 250
  • Pentru teste în valoare de 30 de puncte, N ≤ 20
  • Şirul C se consideră indexat de la 0.
  • Dacă există mai multe soluţii, oricare dintre ele este acceptată.
  • Se garantează că există măcar o soluţie.

Exemplu

sir42.insir42.out
6 2
2 3 3 5 -1 -1
101101
32 2
2 2 6 9 9 9 9 10 10 10 12 13 13 17 18 18 18 18 23 25 25 25 25 25 26 26 27 29 -1 -1 -1 -1
01100010011011000110000101110100
5 3
4 -1 -1 -1 -1
10101
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?