Интересные интересности и задачи/головоломки

[Serge_Bliznykov]

Сообщение от Smitt&Wesson

называть число, нарисованное у какого-то конкретного зека. По условиям задачи, такое число, должно повториться как минимум ещё раз.

Smitt&Wesson, Вы ошибаетесь:

Числа на шляпах могут повторяться

могут - не означает ДОЛЖНЫ повторяться.



Sibedir, а что относить к попыткам подсказать?
Говорить своё число тюремщику на правое или левое ухо - считается подсказкой?
Если нет, то первые семь отвечающих кодируют число, находящееся у восьмого заключённого (левое ухо тюремщика - ноль, правое - один). Восьмой наблюдает за ними, узнаёт и называет своё число.


p.s. а где решение задачи про бочку с квасом?

[Sibedir]

Не, в моей программе от 1 до 7 заключенных. И это не программное, а техническое ограничение. Программа делает полный перебор, потому для 100 заключенных не хватит ни памяти, ни времени (100^100 - этож гугол в квадрате).

p.s. а где решение задачи про бочку с квасом?

Где-то здесь: http://www.programmersforum.ru/showp...&postcount=611

[Sibedir]

Говорить своё число тюремщику на правое или левое ухо - считается подсказкой?

Это подсказка. Смысл в том, что заключенные могут вообще увидеть числа 1 раз, а потом их можно развести по разным комнатам. Если ты сможешь запомнить все числа и произвести (наверное им придется делать это в уму) определенные действия над ними, то свобода гарантированна. Подсказывать даже не нужно. 99 чисел вполне достаточно.

[Аватар]

а где решение задачи про бочку с квасом?

[Б,3л,5л]
[Б,0,0]->[Б,0,5]->[Б,3,2]->[Б,0,2]->[Б,2,0]->[Б,2,5]->
[0,2,5]->[7,0,0]->[4,3,0]->[4,0,3]->[1,3,3]->[1,1,5]->[1,1,0]->[0,1,1]

[Sibedir]

Два заключенных. Один называет число которое видит, второй то которое видит минус 1. (нумерация с 0)
Развиваем тему до 3-х заключенных
Обобщаем на любое их количество.

[Smitt&Wesson]

могут - не означает ДОЛЖНЫ повторяться.

Согласен.

Каждый будет видеть числа на всех остальных заключённых, но не сможет увидеть число на собственной шляпе.

Тогда могу предложить более сложную стратегию. Каждый зек, подсчитывает, все числа от 1 до 100 и если какая-то цифра в списке отсутствует, значит число не повторяется, а находится на его шляпе. Он называет тсутствующее число.
Алгоритм для всех остальных такой. Первый вышедший, назывет наибольшее число из первого десятка. Второй, на единицу меньше и так далее. После выхода к тюремщику 10-го зека, счёт повторяется, опять с наибольшего из первого десятка. Как минимум, одни и те же цифры для 100 заключённых будут повторены по 10 раз.
Возможно этот алгоритм не даёт 100% попадания, но шансы угадать цифру, хотя-бы один раз, достаточно высоки.

[Sibedir]

Не пойдет. Они друг друга не лышат.

[Аватар]

Тогда могу предложить более сложную стратегию. Каждый зек, подсчитывает, все числа от 1 до 100 и если какая-то цифра в списке отсутствует, значит число не повторяется, а находится на его шляпе. Он называет тсутствующее число.

Все пронумерованы единичкой. Алгоритм не работает.
Второй алгоритм ни чем не отличается от называния случайного числа от 1 до 100.

Оказывается есть в сети решение, кому интересно - вот рассуждения
http://elementy.ru/problems/499

[Poma][a]

p.s. а где решение задачи про бочку с квасом?

Фишка(изюминка) была в деньгах и в возможности вылить квас и бочки, тем самым получить 3 сосуда и уже от них плясать (что не составит труда)

Оказывается есть в сети решение, кому интересно - вот рассуждения

Так много букф.. Мне решение by Abstraction больше нравится

[Аватар]

Мне тоже решение Abstraction понравилось, особенно слово элементарно. Совершенно непонятен способ нахождения Fk. Возможно озарение