|
|
| Show all threads Hide all threads Show all messages Hide all messages | | TLE 3 | Danny | 1448. Lighting in Hogwarts | 27 Oct 2019 15:25 | 1 | TLE 3 Danny 27 Oct 2019 15:25 | | What method I have to use? | Neo Nomaly | 1448. Lighting in Hogwarts | 13 Aug 2017 23:23 | 3 | 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. Пожалуйста, не сдавайте задачу, не понимая своё решение!!!
Это хорошая математическая задача из темы на конструктив.
Во-первых, покажем, что решение всегда существует.
Для 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 | | please,give me correct answers | tester | 1448. Lighting in Hogwarts | 28 Jul 2008 22:18 | 6 | My AC program produces following answers:
1000100010001000100010001000100010001000
100100010010001001000100010010001001000100100
1101010101 Re: wa tester 29 Sep 2006 01:18 Thakns .
mine is:
1>> 0010001000100010001000100100010010001000
2>> 001001001001001001001001000100100010010001000
3>> 1010101011
I think my outputs correct but I got WA(3).
Please give me difficult tests.
Edited by author 07.10.2006 20:19 Re: wa Snetch 1 Jul 2007 16:57 100
51
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010 40 25
0010001000100010001000100010001000100010
40 28
0100010001001000100010010001000100100010
10 55
1010101101
(AC) 100 51
1010101010101010101010101010101010101010101010101011010101010101010101010101010101010101010101010101 | | Why WA 3 | test | 1448. Lighting in Hogwarts | 8 May 2008 20:32 | 3 | maybe someone knows what is this test about? Give me some tests please.
I've WA on test 3.
Edited by author 25.07.2006 16:59 Re: Why WA 3 Olympic Bear (Nikolay Dubchuk) 8 May 2008 20:32 | | Stupid greedy works! | Alexander Kouprin | 1448. Lighting in Hogwarts | 4 May 2007 03:11 | 1 | if answer is not 000..000 then first kerosin lamp always be enabled! | | Incorrect example? | Pasky | 1448. Lighting in Hogwarts | 23 Dec 2006 14:15 | 2 | My AC program returns:
10
33
1001001001
Why? For each segment of the corridor comprising L torches the number of ignited torches differs from L*b/100 by not more than 2.
Для любого отрезка коридора количество включенных светильников отличалось от числа L*b/100 не более, чем на 2 |
|
|
|
