Обсуждение @ 1448. Освещение в Хогвартсе @ Timus Online Judge

Danny TLE 3 // Задача 1448. Освещение в Хогвартсе 27 окт 2019 15:25

Neo Nomaly What method I have to use? [2] // Задача 1448. Освещение в Хогвартсе 26 мар 2006 16:30

Peter Ivanov Re: What method I have to use? [1] // Задача 1448. Освещение в Хогвартсе 20 авг 2006 04:18

The only method I used to solve it was the intuition.
I hope anyone who knows a proof of any solution (I think there are many) will expain it.

Felix_Mate Re: What method I have to use? // Задача 1448. Освещение в Хогвартсе 13 авг 2017 23:23

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

Это хорошая математическая задача из темы на конструктив.
Во-первых, покажем, что решение всегда существует.
Для 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

tester please,give me correct answers [5] // Задача 1448. Освещение в Хогвартсе 28 сен 2006 23:03

test Why WA 3 [2] // Задача 1448. Освещение в Хогвартсе 2 апр 2006 12:19

Alexander Kouprin Stupid greedy works! // Задача 1448. Освещение в Хогвартсе 4 май 2007 03:11

Pasky Incorrect example? [1] // Задача 1448. Освещение в Хогвартсе 22 дек 2006 10:46

Обсуждение задачи 1448. Освещение в Хогвартсе