Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Интересные и занимательные задачи по программированию > интересные задачи


Автор: Samotnik 15.6.2011, 00:19
Возможно боян, случайно наткнулся  http://habrahabr.ru/blogs/zadachki/69558/ smile 
Цитата

Заведующий концлагерем вызывает к себе 5 осужденных и говорит:

"У вас будет время до вечера чтобы создать план действий, но уже завтра вы будете находиться в разных камерах и никогда не будете встречаться. У нас в лагере есть Ленинская комната, в которой на столе лежат 2 книги: "Капитал" Маркса и "Анти-Дюринг" Энгельса.

Со следующей недели я буду выбирать одного из вас и водить его в Ленинскую комнату на политинформацию. Читать ничего не надо, но нужно будет обязательно взять любую (но только одну) из книг и перевернуть ее (с тыльной стороны на обложку или наоборот). Кроме вас в Ленинскую комнату никто ходить не будет. Выбирать заключенных я буду как мне хочется: например, сегодня первого три раза свожу, а завтра всех по очереди, а послезавтра обойдетесь.

Рано или поздно каждый из вас побывает в Ленинской комнате. Так вот, любой из вас в любое время может сказать "Мы все здесь уже были!". Если окажется, что он прав, вы все будете освобождены. Если нет - расстреляны."

Что же делать осужденным, ведь время до вечера еще есть?


Цитата

1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку и предложили им ускорить процесс своего освобождения. Итак, в тюрьме есть камера с висящей лампочкой. Лампочку можно включить или выключить. Каждый день, начиная с 1-го сентября тюремщик будет запускать одного заключённого в эту камеру. В этот момент зэк сможет увидеть, горит ли лампочка.
У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?» Если зэк отвечает «нет», игра продолжается.
Если зэк отвечает «да» и это правда — всех выпускают на волю в тундру. Если же это неправда — высшая мера наказания для всех.
Тюремщики могут выбирать заключенных вразброс и с повторениями. Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
Найти оптимальную стратегию поведения каждого заключенного с тем, чтобы их выпустили пораньше.

Автор: Quotter 25.6.2011, 00:21
/ответ к первой.\

план действий.

Один из осужденных будет переворачивать книгу "Капитал"

Второй "Анти-Дюринг"

Третий будет менять местами "Капитал" и "Анти-Дюринг"

Четвертый будет составлять в стопку и переворачивать книгу "Капитал"

Пятый с этой же стопки будет переворачивать книгу "Анти-Дюринг"


/ответ к первой.\ только не 5, а 19 осужденных

1 будет переворачивать "Капитал" (и класть на стол в середину)

еще 1 будет переворачивать "Анти-Дюринг" (и класть рядом с книгой "Капитал")

еще 1 будет составлять их в стопку.

4 из осужденных будут переворачивать "Анти-Дюринг" на углу стола (ну один из них на левом нижнем второй на правом и т.п.)

4 других будут переворачивать её под столом, но во внутренней его стороне.

еще 4 будут переворачивать их по внешней стороне стола, но по верхней и нижней грани.

еще 4 будут переворачивать их по левой и правой грани.

p.s.
пример в картинке. http://radikal.ru/F/s004.radikal.ru/i207/1106/5b/1a87078ed29f.jpg.html

Автор: Nostr 3.7.2011, 17:26
Не верно. Тут есть обобщение для N.
Нужно выбрать счетовода, который будет считать сколько было переворото книг. Каждый перевернет лишь 1 раз.
Счетовод возвращает книгу назад, все легко

Автор: Quotter 3.8.2011, 11:32
Цитата(Nostr @ 3.7.2011,  17:26)
Не верно. Тут есть обобщение для N.
Нужно выбрать счетовода, который будет считать сколько было переворотов книг. Каждый перевернет лишь 1 раз.
Счетовод возвращает книгу назад, все легко

Так тут никто не будет знать была ли книга перевернута или нет. Так что какой тут смысл от счетчика для переворотов книг ????

Смотри один зашел думает была ли она перевернута или нет Хммм... дай как переверну.
И так думают все последующие.

И вот тебе еще пример 1ый человек зашел повернул, запомнил как лежат. 2ой зашел перевернул ту же. 3ий зашел перевернул то же эту книгу. И для 1го положение будет такое как будто перевернул он. И это значит что он не будет знать что до него кто-то был (он сможет предположить, но это будет не точно)

Автор: Akina 3.8.2011, 13:04
Цитата(Quotter @  25.6.2011,  01:21 Найти цитируемый пост)
план действий.

Один из осужденных будет переворачивать книгу "Капитал"

Второй "Анти-Дюринг"

Третий будет менять местами "Капитал" и "Анти-Дюринг"

Четвертый будет составлять в стопку и переворачивать книгу "Капитал"

Пятый с этой же стопки будет переворачивать книгу "Анти-Дюринг"

У них нет разрешения на перемещение книг - только переворачивать. Так что менять местами или составлять в стопку не получится.

Решение 1 задачи.

Первый должен оставить первую книгу лицом вверх корешком вправо.
Второй - лицом вверх корешком влево.
Третий и четвёртый соответственно лицом вниз.

Т.е. если первую книгу нельзя перевернуть так, чтобы она оказалась в положении "как надо оставить" - переворачивается вторая, иначе первая.

Пятый - арбитр. Если он видел все 4 положения (при этом он отбрасывает самое первое положение первой книги и начинает учёт только тогда, когда оно первый раз изменилось) - он говорит, что все побывали в комнате.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)