Задачка

[vilgeforce]

Есть две комнаты, разделенные перегородкой. В одной комнате сидит негр с листком бумаги, ручкой и калькулятором. Во второй комнате - экспериментатор. Со стороны экспериментатор есть кнопка и маленький дисплей всего на 2 цифры (это важно). Что в комнате с негром - неизвестно, но известно, что при нажатии на кнопку негр должен взять последнее

Comments

[vilgeforce]

На листке у негра написано число 168. 168 * 234617 = 39415656, на листок он запишет 39415657, а в окошке будет 41. Что-то я не увидел у тебя про такой случай :-)

[miiir]

Ну так это же семёрка, то есть третий ход. А следующим ходом будет ноль, а ещё через один ход ноль в окошечке будет виден - всё станет нулями.

[miiir]

(Забыл про прибавление единицы в условии, потому и решил:)

Поскольку всё умножается на *****7, то последняя цифра меняется редко.
В первый ход это 1.
Во второй ход это 7 (так как 7 x 1 = 7)
В третий ход это 9 (так как 7 х 7 = 49)
В четвёртый ход это 3 (так как 7 х 9 = 63)
В пятый ход это снова 1 (так как 3 х 7 = 21)

Следовательно, множители идут в последовательности 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3.

В окошке видны пятая и шестая цифры. Если негр умножает их на единицу, они не изменяются. Так определяется начало цикла (минимум - в один ход, максимум - в четыре). Если цифры после начала цикла три раза изменяются, а в четвёртый - нет, всё верно. Если цифры изменяются четыре раза подряд - ошибка.

(С единицей всё гораздо проще 1, 8, 7, 0, 1. При умножении на ноль всё обнуляется (если негр признаёт ноль и пользуется 10-ричной системой), следующим ходом прибавляется единица, и тогда если сразу после двух нулей в окошечке будут цифры 23, то остальные цифры - 4617. А нули - они и есть нули).

[vilgeforce]

"В первый ход это 1." - Из чего это следует? При умножении любого числа на *****7 где именно ты ожидаешь увидеть единицу?

[miiir]

Рано или поздно она возникает.

[miiir]

Увидеть её я и не ожидаю. Ожидаю увидеть эффект от неё: не-изменение цифр после нажатия кнопки.

[randir_spb]

А тупо полным перебором?

[vilgeforce]

Это решение уже реализовано. Но хотелось бы аналитического или хотя бы ограничений на полный перебор.

[randir_spb]

У меня получается перебор 10000*число шагов, с моей точки зрения достаточно.
Но подумаю.

[vilgeforce]

Ага. Всего-то надо перебрать все неизвестные цифры, то есть 4. Вот дополнительное ограничение на возможный диаппазон мне не дается :-(

[mtve]

я не понял задачу или трёх нажатий всегда достаточно?
например, если были видны числа 00 13 43 52 значит вначале у негра было 755.
по второй задаче - если негр выдал 3 или 4 числа которых нет в таблице на ~10MB памяти, то он ошибся.

[vilgeforce]

Ну я предполагаю что трех достаточно, да. Но как из нескольких чисел, которые видны получить то что было в начале?

[mtve]

как написали выше - перебор для 10000 вариантов. формулу, да, можно поискать, сейчас подумаю.

[vilgeforce]

Перебор уже и так сделан, это неинтересно...