Пожалуйста, не сдавайте задачу, не понимая своё решение!!!

Это хорошая математическая задача из темы на конструктив.
Во-первых, покажем, что решение всегда существует.
 Для k=1 утверждение справедливо.
 Пусть уже построена последовательность s1...sk, удовлетворяющая условию задачи.
 Пусть cij=кол-во 1 на [i,j].
 Покажем, что можно добавить 0 или 1 в конец, чтобы полученная последовательность также была решением. Предположим противное: при добавлении 0 есть подотрезок [i,k+1], где cik>(k-i+2)b/100+2 (1) или cik<(k-i+2)b/100-2 (2) и при добавлении 1 есть подотрезок [j,k+1], где cjk>(k-j+2)b/100+1 (3) или cjk<(k-j+2)b/100-3 (4).
Заметим, что (1) и (4) невозможны (по индукции |cik-(k-i+1)b/100|<=2 => cik<=(k-i+1)b/100+2 и |cjk-(k-j+1)b/100|<=2 => cjk>=(k-j+1)b/100-2).

Итого получаем (2) и (3) одновременно:
cik<(k-i+2)b/100-2, cjk>(k-j+2)b/100+1 => cjk>cik => j<i.
Рассмотрим отрезок [j,i-1]. По индукции cj,i-1=cjk-cik удовлетворяет условию |(cjk-cik)-(i-j)b/100|<=2 => cjk<=cik+(i-j)b/100+2<(k-i+2)b/100+(i-j)b/100=(k-j+2)b/100.
=> cjk<(k-j+2)b/100. С другой стороны, выполнено (3)-противоречие => 0 или 1 даёт решение длины к+1.


Как сконструировать решение? Из док-ва видно, в каких местах возникают проблемы. Когда можно добавить 0 (если нельзя => нужно добавить 1-это даст решение по док-ву)?
0 можно добавить <=> для 1<=i<=k выполнено (k-i+2)b/100-2<=cik<=(k-i+2)b/100+2. Второе неравенство выполнено (т.к. cik<=(k-i+1)b/100+2). Поэтому нужно (k-i+2)b/100-2<=cik. Когда это условие нарушается? Оно нарушается <=> существует такое 1<=i<=k, что cik<(k-i+2)b/100-2 <=> cik<(-b/100)i+(2kb/100-2).Заметим что cik неубывает, а (-b/100)i+(2kb/100-2) строго убывает => нарушение происходит <=> i=1 <=> c1k<-b/100+2kb-2=kb/100-2 <=> 100*c1k<kb-200. В этом случае 0 брать нельзя.


Edited by author 13.08.2017 23:28

100
51
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010

100 51
1010101010101010101010101010101010101010101010101011010101010101010101010101010101010101010101010101

check on test:
45
28