Дневник еврейского расовог -
[Recent Entries][Archive][Friends][User Info]
06:47 pm
[Link] | |
|
|
![[User Picture]](http://lj.rossia.org/userpic/203759/26701) | From: | ogles |
Date: | January 2nd, 2019 - 11:26 am |
---|
| | | (Link) |
|
гасим свет в начальном вагоне. в каждом следующем вагоне включаем свет. считаем пройденные вагоны (х) и количество освещенных вагонов, начиная с последнего, где мы включили свет (y). останавливаемся когда x=2y. Ответ x (может быть с точностью до одного вагона, лень уточнять).
From: | (Anonymous) |
Date: | January 2nd, 2019 - 01:27 pm |
---|
| | | (Link) |
|
> где мы включили свет откуда знаешь? нагадил там?
Можно начать считать после того, как включил свет.
From: | (Anonymous) |
Date: | January 2nd, 2019 - 01:37 pm |
---|
| | | (Link) |
|
откуда знаешь что ты везде включил свет?
Вот-вот, поэтому алгоритм можно обмануть, как я пишу ниже.
Там автор предполагает, наверное, что он всегда успеет добежать до первого вагона, пока его счетчик считает.
Обозначаю темные вагоны #, а светлые вагоны O, посложение счетчика ^. А дальше значения переменных перед предстаящим действием. Вот простой пример:
#O ^___x=0,y=0 #O _^__x=1, y=0 #O ^___x=2, y=0 OO _^__x=3, y=1 OO ^___x=4, y=2
Фэйл, x=4, y=2, наш ответ 4, правильный ответ y. Поэтому, очевидно ответом должен быть y, а не число пройденных шагов. Но даже если отвечать y, То по теореме Каледина алгоритм даст неверный ответ на входе #O#OOO, например. |
|