|
Найти пятничного кота | ☑ | ||
---|---|---|---|---|
0
Ненавижу 1С
гуру
13.11.15
✎
09:47
|
Перед Вами расположены 100 закрытых коробок в ряд, в одной из которых спрятался пятничный кот. Вы можете открыть одну из коробок и проверить наличие пятничного кота. Если его там не оказалось, то после закрытия этой коробки пятничный кот обязательно незаметно перебирается в одну из соседних (относительно той, в которой он был) коробок.
Можно ли вообще однозначно определить в какой коробке пятничный кот за конечное число ходов-открытий коробок? Если да, то сколько требуется действий? |
|||
63
Enterprise
13.11.15
✎
10:40
|
(59) Что такое прямой и обратный проход?
|
|||
64
Dotoshin
13.11.15
✎
10:40
|
(59) Допустим открываем первую коробку, а кот вот второй коробке, закрываем первую, кот прыгает в третью, открываем вторую и т.д., пока не дойдем до 99, допустим кот к этому моменту сидит в сотой, когда ты закроешь 99 он перепрыгнет из сотой в 99-ю и ты его все равно не поймаешь.
|
|||
65
Ненавижу 1С
гуру
13.11.15
✎
10:41
|
(63) это из (53)
|
|||
66
Ненавижу 1С
гуру
13.11.15
✎
10:42
|
(64) мы 99-ю же дважды открываем
|
|||
67
Dotoshin
13.11.15
✎
10:44
|
(66) Так он мог и раньше в обратном направлении побежать, в условиях же он не ограничен в смене направления
|
|||
68
PR третий
13.11.15
✎
10:44
|
(25) С хрена ли? А кот был в 4, 3, 2, 1. Поймал?
|
|||
69
PR третий
13.11.15
✎
10:45
|
При постановке задачи в (0) задача нерешаема.
|
|||
70
Dotoshin
13.11.15
✎
10:46
|
Засада в том, что кот перемещается при закрытии коробки. То есть его можно поймать только случайно.
|
|||
71
letni88
13.11.15
✎
10:47
|
решения нет) кот очень хитр
|
|||
72
Лодырь
13.11.15
✎
10:47
|
Вообще 197 открытий/закрытий? Поскольку, когда откроем 99 и его там не окажется, то он после закрытия 99 коробки переберется в нее. Следовательно открывать ее не надо, мы и так знаем что он там.
|
|||
73
FuriKuri
13.11.15
✎
10:47
|
Мне кажется нельзя его поймать впринципе. Например мы решили открыть 2 (или любую, кроме 1 или 100 коробки) коробку два (или бесконечное число) раза. И на самый последний раз, когда закрываем коробку, он может быть в соседней и переместиться в нашу закрытую коробку. Далее мы опять открываем ее кучу раз, и после последнего закрытия, кот опять же может быть в соседней и переместится в нашу закрытую. То есть кот всегда может быть на шаг позади. Чистый рандом.
Единственный вариант когда можно кота поймать, это все время открывать 2 или 99 коробку, и угадать когда он переместится в нашу, и выбрать 3 (98), чтобы кот перебрался в 1 (100), и тогда открывать 2 (99). Но опять же рандом. Вобщем словить кота при данном условии нереально! |
|||
74
Junior1s
13.11.15
✎
10:48
|
за 200 ходов разве нет ? :)
|
|||
75
Dotoshin
13.11.15
✎
10:48
|
(71) Да, кошки они такие их только ответной хитростью можно взять :)
|
|||
76
Лефмихалыч
13.11.15
✎
10:50
|
(0) если кот может перелезть в ту коробку, которую ты только что открывал, то задача не имеет решения при числе коробок более 2х
|
|||
77
Лодырь
13.11.15
✎
10:51
|
(76) 2 раза подряд открой коробку номер 1, после этого открой коробку два и ты можешь быть твердо уверен что кот не в 1 в этот момент.
|
|||
78
Лефмихалыч
13.11.15
✎
10:52
|
(77) кот может перелезть в коробку после того, как ты ее закроешь во второй раз
|
|||
79
regi1984
13.11.15
✎
10:53
|
(53) Решение найдено ведь уже.
|
|||
80
b_ru
13.11.15
✎
10:53
|
(76) Она не имеет 100% решения даже при числе коробок равном 2.
Это как гарантированно выкинуть решку за конечное число ходов. |
|||
81
Timon1405
13.11.15
✎
10:54
|
(68) Да поймал на 5м ходу. И что это за тон?
|
|||
82
Лефмихалыч
13.11.15
✎
10:54
|
(80) с учетом того, что кот ОБЯЗАН переместиться после закрытия коробки, то при двух коробках он гарантированно найдется после второго открытия одной и той же коробки. А вот в трех его можно уже и не найти
|
|||
83
b_ru
13.11.15
✎
10:55
|
(82) А ну да, обязательно же перемещается.
|
|||
84
FuriKuri
13.11.15
✎
10:56
|
(82) и при трех найдется за 2 хода.
|
|||
85
Лодырь
13.11.15
✎
10:56
|
(82) при трех достаточно вторую коробку открыть два раза.
|
|||
86
Ненавижу 1С
гуру
13.11.15
✎
10:56
|
Решение. Всего 198 открытий-ходов.
Перенумеруем подряд коробки от 1 до 100. Открываем в 2 акта. Акт 1: открываем с 1 по 99 коробки подряд Акт 2: открываем с 99 по 1 коробки подряд Акт 1. Если кот не собирается пересекать "фронт открываемых коробок", то мы его загоняем в 100-ю и так как 99-ю открываем дважды, он будет пойман. Если кот пересекает "фронт открываемых коробок", то значит когда мы открывали N-ю он сидел в (N+1)-й и переползает в N-ю. Итак, значит когда мы открываем четную коробку, кот сидит в нечетной и наоборот. Акт 2. На начало акта кот сидел в нечетной коробке. Мы снова открываем 99-ю и кот из нечетной переползает в четную. Теперь открывая четную кот сидит в четной, то есть четности совпадают. И снова пересечь "фронт открываемых коробок" кот не сможет. |
|||
87
Лефмихалыч
13.11.15
✎
10:56
|
(84) только случайно. Но случайно он может и за один ход найтись при любом количестве коробок.
|
|||
88
Лефмихалыч
13.11.15
✎
10:57
|
(86) где в условии сказано, что код обязательно только в одну сторону идет? Из чего следует, что он не может 99 раз переходить из 1й коробки во 2ю и обратно?
|
|||
89
b_ru
13.11.15
✎
10:57
|
Тогда и при 4 поймаем.
2 раза открываем 2ю. Если не поймали, то кот либо в 3, либо в 4. 2 раза открываем 3ю - пойман. |
|||
90
Ненавижу 1С
гуру
13.11.15
✎
10:58
|
+(86) фактически это решение дано RomanYS в (53) я просто причесал немного
|
|||
91
Лефмихалыч
13.11.15
✎
10:59
|
(89) >2 раза открываем 2ю. Если не поймали, то кот либо в 3
да, но только он там искючительно, пока коробка 2 открыта. После закрытия он уже может быть и в3, и в 4, и в 2, и в 1 |
|||
92
Timon1405
13.11.15
✎
10:59
|
(86) как-то неочевидно, что за меньшее количество ходов нельзя
|
|||
93
Ненавижу 1С
гуру
13.11.15
✎
10:59
|
(88) не обязательно в одну сторону, может и так, но ты обрати внимание на инвариант четности в решении
|
|||
94
Ненавижу 1С
гуру
13.11.15
✎
11:00
|
(92) согласен, минимум не доказан
|
|||
95
Лефмихалыч
13.11.15
✎
11:01
|
(93) тогда это решение уже на 3х коробках не работает
|
|||
96
b_ru
13.11.15
✎
11:02
|
(95) По ходу оно не работает на нечетном числе коробок, но работает на четном
|
|||
97
Ненавижу 1С
гуру
13.11.15
✎
11:02
|
(95) работает, открываем 1,2,2,1
|
|||
98
Лодырь
13.11.15
✎
11:03
|
(97) 1,2,2 уже сработает
|
|||
99
Лефмихалыч
13.11.15
✎
11:04
|
(97) А на 4х?
|
|||
100
Wirtuozzz
13.11.15
✎
11:04
|
100
|
|||
101
Ненавижу 1С
гуру
13.11.15
✎
11:05
|
(99) 1,2,3,3,2,1 надеюсь ты общий алгоритм уже понял?
|
|||
102
Лодырь
13.11.15
✎
11:05
|
кстати есть мнение что при обратном проходе нет необходимости идти до первой коробки.
|
|||
103
extrim-style
13.11.15
✎
11:06
|
решать нужно на 4 коробках
решение основывается на крайних коробках, после нахождения в которых кот обязан переползти в предпоследнюю решаем на 4х: открываем --- где может быть 3 - 124 3 - 123 2 - 13 2 - 24 3 - 3 - кот пойман в любом случае далее распространить эту методику на 100 (мне щас некада дальше думать) |
|||
104
Лодырь
13.11.15
✎
11:06
|
его там не может быть из за четности.
|
|||
105
Timon1405
13.11.15
✎
11:06
|
(86) Раз во втором акте четность стала совпадать, значит он попадется на второй коробке, а не на первой, значит ходов будет 197(до первой коробки не доберемся)
|
|||
106
Ненавижу 1С
гуру
13.11.15
✎
11:08
|
(102) кстати из четности да, уменьшаем до 197
|
|||
107
regi1984
13.11.15
✎
11:09
|
(101) Есть мнение, что первую коробку нет необходимости открывать при первом проходе, экономим один ход.
|
|||
108
Лефмихалыч
13.11.15
✎
11:09
|
При 4 тоже работает. Хмм...
|
|||
109
Ненавижу 1С
гуру
13.11.15
✎
11:10
|
(107) опять да, таки 196! спасибо
|
|||
110
Лодырь
13.11.15
✎
11:10
|
Как видим метод монте-карло будет эффективнее )
|
|||
111
Лодырь
13.11.15
✎
11:11
|
Хоть и не гарантирует результата.
|
|||
112
НоваяВолна
13.11.15
✎
11:13
|
(0) ОТВЕТ 13.... и не говорите, что я не прав... сегодня ПЯТНИЦА??? ... 13 ???
|
|||
113
Ненавижу 1С
гуру
13.11.15
✎
11:21
|
Меньше 196 нельзя. Если меньше, то одну из "некрайних" коробок мы проверяли не более 1 раза. Допусти кот знает о последовательности открытия всё.
1. Есть коробка вообще непроверенная. Кот сидит в ней изначально, делая вылазки в соеднюю слева/справа и возвращаясь в исходную. Если слдующим ходом открываем коробку слева от данной, он идет в правую и наоборот. 2. Есть коробка проверенная 1 раз. По четности кот определяет где ему изначально сесть: в этой коробке или слева/справа, чтобы на нужном ходу открытия не быть в открытой ЭТОЙ коробке. А в остальном действует как в пункте 1. |
|||
114
Мэс33
13.11.15
✎
11:29
|
Буду наступать на коробки ))
|
|||
115
PR третий
13.11.15
✎
12:12
|
(81) Это случайность, попробуй на 6 ячейках, по-твоему алгоритму не поймаешь.
|
|||
116
PR третий
13.11.15
✎
12:12
|
(53) Упс, да, работает :)) Прикольный алгоритм :))
|
|||
117
Domovoi
13.11.15
✎
12:53
|
Задача для 3 класса. Мегопроги не могут сообразить даже когда им дали решение) КВН:)
|
|||
118
Ненавижу 1С
гуру
13.11.15
✎
13:07
|
(117) ну задним число у нас все умные )))
|
|||
119
Diversus
13.11.15
✎
13:07
|
Открываем первую коробку, кот либо там, либо на следующем шаге он будет в соседней. Соседняя коробка для первой одна, т.к. коробки расположены в ряд, значит он будет во второй. Все, задача решена.
Максимум потребуется 2 действия. |
|||
120
PR третий
13.11.15
✎
13:21
|
(117) Для третьего класса? Ню ню.
|
|||
121
PR третий
13.11.15
✎
13:22
|
(119) Возьми с полки пирожок :))
|
|||
122
GomerSimpson
13.11.15
✎
13:29
|
Нужно использовать то, что кот обязан менять четность.
Допустим что мы знаем что кот сейчас в четной коробке. Тогда открываем каждую нечетную по 2 раза. 11335577 и т.д. до конца - кот проскочить нам заспину не может и будет пойман (если верно наше допущение). Если дошли до конца и не нашли, то теперь мы точно знаем что вначале он был в нечетной, аналогичным образом двигаемся назад. Максимум 199-200 открываний. |
|||
123
PR третий
13.11.15
✎
13:30
|
(122) 196 насчитали уже
|
|||
124
Лодырь
13.11.15
✎
13:34
|
(122)
1(3>2) 1(2>1) 3(1>2) 3(2>3) 5(3>4) 5(4>5) .. 99(97>98) 99(98>99) что дальше? |
|||
125
Лодырь
13.11.15
✎
13:34
|
и хрен ты его поймаешь при такой тактике.
|
|||
126
MUXACb
13.11.15
✎
13:36
|
(0) Вопрос по Задорнову- как кот может НЕЗАМЕТНО перемещаться по ЗАКРЫТЫМИ коробками?
|
|||
127
Лодырь
13.11.15
✎
13:37
|
(126) У тебя кот есть?
|
|||
128
Ненавижу 1С
гуру
13.11.15
✎
13:43
|
(126) он же пятничный кот
|
|||
129
GomerSimpson
13.11.15
✎
13:52
|
(124)
Дальше мы получаем важное знание, что сейчас кот сидит в нечетной коробке. Таким образом, при каждом открывании мы знаем 50 коробок где кота быть не может. И т.к. он не может перепрыгнуть через коробку или отстаться в той же, Котэ не уйти, он будет обязательно пойман и кастрирован |
|||
130
Лодырь
13.11.15
✎
14:01
|
(129) В приведенном примере - как ты дальше его поймаешь?
|
|||
131
lopus
13.11.15
✎
14:10
|
А так разве его не поймаем первая коробка 2 раза и на предпоследней однозначно его поймаем. Т.е. 100
|
|||
132
Лодырь
13.11.15
✎
14:13
|
(131) нет
1(3>2) 1(2>1) 3(1>2) 3(2>3) 5(3>4) 5(4>5) .. 99(97>98) 99(98>99) И он в 99 а не в 100 ) а мог быть в любой нечетной. |
|||
133
GomerSimpson
13.11.15
✎
14:19
|
(130)
Ну как дальше, зная что он в нечетной коробке, открываем 99 и если его там нет, то его нет и в соседних 98 и 100. Дальше, зная что он в четной коробке, открываем 98 и, если его там нет, то 97-100 пустые. Дальше, зная что он в нечетной коробке, открываем 97 и, если его там нет, то 96-100 пустые. И т.д. |
|||
134
Господин ПЖ
13.11.15
✎
14:19
|
котэ нагнул 1с-ников
|
|||
135
Локи-13
13.11.15
✎
14:32
|
(134) пускай котэ расскажет как налог на имущество считается, посмотрим кто кого нагнул
|
|||
136
Timon1405
13.11.15
✎
14:34
|
(135) Принес ты курицу домой, отдал 13% котэ.
|
|||
137
ДенисЧ
13.11.15
✎
14:35
|
(136) 13% это подоходный...
|
|||
138
Timon1405
13.11.15
✎
14:36
|
(137) котэ пофигу какой, главное что съедобный
|
|||
139
Ненавижу 1С
гуру
13.11.15
✎
14:40
|
(135) котэ имущества не надобно, он радикально эту проблему порешал
|
|||
140
MaxS
13.11.15
✎
14:43
|
>кот перебирается в одну из соседних (относительно той, в которой он был)
Открывать всегда 25-ю коробку, с вероятностью 50% он там должен появиться. |
|||
141
Casey1984
13.11.15
✎
14:47
|
Какой-то неправильный кот.
|
|||
142
IvaneS
13.11.15
✎
15:47
|
Если кот перемещается между двумя коробками и при приближении границы фронта через коробку, то начинает двигаться в сторону фронта. При таком поведении кота задача не решаема, т.к. КОТ "ХИТРЫЙ". (кот постоянно перемещается межу 9-10, вы открыли 7 и он начинает двигаться в сторону 7, когда вы откроете 7 второй раз он на 8 и следующим шагом сядет 7, а вы откроете 8... В условии не сказано точное поведение КОТА, значит он может быть "ХИТРЫМ"
|
|||
143
Woldemar177
13.11.15
✎
15:57
|
||||
144
Domovoi
13.11.15
✎
16:06
|
(113)может 195?
|
|||
145
Ненавижу 1С
гуру
13.11.15
✎
16:15
|
(144) нет, минимум 196
|
|||
146
Domovoi
13.11.15
✎
16:20
|
На примере 6 коробок.
2,2,3,4,5,5,4 - не закрывая 4 коробку, если котэ не найден то он во 2. макс число 12 ходов, текущее решение 7 - сэкономили 5 ходов. 100*2-5=195 |
|||
147
Ненавижу 1С
гуру
13.11.15
✎
16:32
|
(146) закрыть надо по условию, а вот куда кот после этого пойдет - вопрос
тем более когда ящиков 100 |
|||
148
Ненавижу 1С
гуру
13.11.15
✎
16:33
|
+(147) собственно доказательство (113) это и говорит
|
|||
149
Timon1405
13.11.15
✎
16:38
|
(146) знать что кот сидит во втором ящике в тот момент когда вы открываете 4й ящик и поймать кота - не одно и то же.
|
|||
150
Domovoi
13.11.15
✎
16:41
|
(149)"Можно ли вообще однозначно определить в какой коробке пятничный кот за конечное число ходов-открытий коробок"
Ничего не сказано про поймать. Только про то чтоб определить где сидит кот при открытии коробок. Я нашел при открытии где сидит кот) |
|||
151
Timon1405
13.11.15
✎
16:42
|
*это как отгадать где деньги в двух шкатулках в поле чудес: если не угадал с первого раза, ты точно знаешь что они во второй коробке, но денег не получишь
|
|||
152
wertyu
13.11.15
✎
16:43
|
а теперь та же задача, но коробки расположены квадратом 10 на 10
|
|||
153
Timon1405
13.11.15
✎
16:44
|
*то после закрытия этой коробки пятничный кот обязательно незаметно перебирается в одну из соседних - в конце хода он перебрался в соседнюю, вы не успели сообщить его состояние в течении своего хода
|
|||
154
Domovoi
13.11.15
✎
16:52
|
(153)В условии написано "за конечное число открытий коробок" В задачи закрытия это середина хода.
Но я понимаю после уточнения условия надо чтоб коробка закрылась, не настаиваю ни на чем. |
|||
155
Ненавижу 1С
гуру
13.11.15
✎
17:03
|
(152) не взлетит, нет коробок с одним выходом
|
|||
156
Dotoshin
13.11.15
✎
17:12
|
Я нашел пятничного кота http://mtrpl.ru/wp-content/uploads/2015/04/кот-в-коробке-3.jpg
|
|||
157
MaxS
13.11.15
✎
17:40
|
(156) "Вы можете открыть одну из коробок и проверить наличие пятничного кота"
Если он там оказался, коробку Вы уже не сможете закрыть. ;) |
|||
158
wertyu
13.11.15
✎
17:45
|
(155) а если за основу взять решето эрастофена сто первых элементов и тоже оквадратить (с пропусками)
|
|||
159
wertyu
13.11.15
✎
17:46
|
эратосфена*
|
|||
160
Mort
13.11.15
✎
18:08
|
Чётные и нечётные коробки...
|
|||
161
Mort
13.11.15
✎
18:10
|
А дальше понятно я думкю
|
|||
162
Михаил Козлов
13.11.15
✎
18:39
|
Хорошая задача, можно с внуками играть (как в морской бой). Только, боюсь, быстро просекут стратегию охотника.
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |