26 дек. 2011 г.

Аукцион с камнями

Добрый день.

За новогодним столом бывает здорово поиграть в какую-нибудь весёлую игру. Например, можно устроить аукцион, в котором побеждает тот, кто сможет закодировать пару чисел из наибольшего диапазона. Здорово звучит?

Цитата из книги «Что делать, если вас не считают занудой»: «Встретив филологов или историков, расскажите им анекдот про марсианина. Обязательно объясните им, почему это смешно. Убедите их поделиться этим анекдотом с друзьями. Проконтролируйте, чтобы они правильно объяснили своим друзьям, почему этот анекдот смешной».

Но возвращаемся к нашему аукциону. Недавно Константин Кноп напомнил чудесную формулировку (осторожно, там в комментариях сказано уже слишком много!):

Секретный код к любому из сейфов ФБР — это натуральное число от 1 до 1700. Двое шпионов узнали по одному коду каждый и решили обменяться информацией. Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней. Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять первый и так далее до тех пор, пока камни не кончились. После этого шпионы разошлись. Каким образом могла быть передана информация? (Шпионы не сказали друг другу ни слова.) (Авторы - Дмитрий Челкак и Константин Кохась, СПбМО 2002, отборочный тур, 10 класс)

Мне в ней не нравятся две вещи:
- наших разведчиков назвали шпионами,
- задана граница 1700.

Поэтому давайте чуть-чуть переформулируем задачу:
- два человека знают целые числа из диапазона от 1 до N,
- они поочерёдно пишут на доске положительные целые числа, пока сумма всех записанных чисел не станет равна 26,
- давным давно они учились в одном классе, поэтому заранее договорились, как кодировать данные.

Вопросы:
1. Как они могли бы обменяться парой чисел при N = 1700?
2. Для какого максимального N вы можете придумать способ кодирования?


Эта задачка хороша тем, что когда кажется, что «ну уж дальше N увеличить невозможно», обязательно находится кто-то, кто опять смог поднять верхнюю границу :)

(Кстати, не так давно мы решали другую забавную школьную задачку, имеющую отношение к теории кодирования)

Хорошего начала предпраздничной недели!

89 комментариев:

  1. Они могли бы использовать двоичный код.
    Тогда, если предоставиь каждому равные возможности, т.е. по 13 разрядов, то можно записать числа от 0 до 8191.

    ОтветитьУдалить
  2. Akademic, идея понятна, но у них нет 13 разрядов.

    ОтветитьУдалить
  3. Сразу попытаюсь вбросить оценку сверх на N во втором вопросе: 5792.

    Всего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), а значит совместно они могли закодировать число не более чем 2^25. Так как не должно существовать двух пар чисел, для которых случится одна и та же ситуация, то N <= floor(sqrt(2 ^ 12.5)) = 5792

    ОтветитьУдалить
  4. Daniel Burdakov,
    верно, различных способов кидать камни у них 2^25=33554432. Так мы посчитали количество информации, которое можно передать таким образом (мы ранее уже делали подобные упражнения). Поэтому теоретический максимум N составляет целая часть корня из этой величины, т.е. 5792.

    ОтветитьУдалить
  5. Анонимный26.12.2011, 12:46

    Разве нету 13 разрядов?
    По такой системе: Сначала выписываем младший разряд где выставлен бит, потом номер разряда следующего бита - номер разряда первого выставленного бита.
    Для 4160 (1000001000000) будет написано:
    6;
    6;

    Пожалуй, если можно кинуть 0 камней даже 14 бит поместится.

    ОтветитьУдалить
  6. Уважаемый аноним,
    я не в полной мере понимаю, как использовать Ваш способ кодирования в этой задаче.

    Пожалуйста, объясните подробнее. Отмечу только пару моментов:
    1) По условию кидать можно только положительное количество камней, поэтому 0 нельзя,
    2) Число бросков у обоих участников должно быть одинаковым или отличаться на единицу (потому что они кидают камни поочерёдно, пока те не кончатся).

    ОтветитьУдалить
  7. Анонимный26.12.2011, 13:12

    Уважаемый Илья,
    Я не осознал влияние второго условия, свое невнятно описанное решение снимаю как неверное.

    ОтветитьУдалить
  8. "Число бросков у обоих участников должно быть одинаковым или отличаться на единицу (потому что они кидают камни поочерёдно, пока те не кончатся). "

    Вы смешали две задачи - оригинальную (где такого условия и близко не было) и свою (возможно, вы свое условие недописали)? Если они поочередно пишут положительные числа, то нет проблемы написать (А и Б - люди) А1, Б3, А7, Б4 ... А если они поочередно кидают камни, то тоже непонятно, откуда ограничение.

    ОтветитьУдалить
  9. Есть способ закодировать числа от 1 до 1716.

    Разведчики решили поделить камни по-честному и каждый будет бросать половину камней 26/2=13.

    Количество способов записать число k в виде суммы n чисел равно binom(k-1,n-1) == количество информации передаваемой за n-ходов.

    Доп. ограничение на кол-во ходов: n2 = n1 или n1-1

    В итоге:
    1. первый кидает 13 камней за 7 или 8 ходов (792+924=1716 вариантов)
    2. второй кидает 13 камней за (6 или 7) или (7 или 8) ходов (792+924=1716 вариантов в обоих случаях)

    PS binom(13-1,n-1) для n=1..13
    1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1

    ОтветитьУдалить
  10. Дополнение.
    выше немного не ясно как они узнают кто сколько ходов хочет сделать.
    Более точный вариант:
    1. Оба делают по 7 или 8 ходов.
    2. Если первый делает 8, то второй 7 или 8, как обычно.
    3. Если первый делает 7, а второму нужно 8, то последний ход второго делает первый, те выкидывает оставшиеся камни.
    (это не вносит неопределенность, тк первый уже выбросил свои 13 камней)

    ОтветитьУдалить
  11. Eugene Mayevski, Вы спрашиваете «Вы смешали две задачи - оригинальную (где такого условия и близко не было) и свою (возможно, вы свое условие недописали)?», как будто в заметке предложены две разные задачи. Это одна и та же задача, просто сформулированная двумя разными способами (потому что одни людям удобнее и интереснее мыслить в терминах камней, а другим - в терминах чисел на доске).

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

    Я вёл речь именно о количестве чисел, которое каждый из них напишет (эти количества не могут отличаться больше, чем на один). Ну или о количестве бросков, которые они сделают (тоже должны совпадать или отличаться на один).

    vayun,
    отлично, для N=1716 решение предъявлено.

    Но ясно же, что можно больше. Кто улучшит этот результат? :)

    ОтветитьУдалить
  12. Анонимный27.12.2011, 16:23

    Каков шаг аукциона? Если 1, то у меня 1717 :-)
    Дарья

    ОтветитьУдалить
  13. Анонимный28.12.2011, 7:29

    Честно говоря, не понял при чем здесь
    2^25, 5792, 1716. Объясните пожалуйста по подробнее. Желательно на примере.

    Заметил что 26=3+5+7+11, а куда дальше идти непонятно. Возможно в направлении китайской теоремы.

    Я думаю надо максимально полно использовать предыдущие шаги, сделанные "собеседником", т.е. чтобы шаг 1 собеседника 2 зависел от шага 1 собеседника 1.

    ОтветитьУдалить
  14. Дарья,
    шаг аукциона не задан, поэтому 1 вполне подходит :)

    Уважаемый аноним,
    в одном комментарии Вы задали несколько больших вопросов, но не указали, как глубоко не понимаете ответы на них. Лучше задавать конкретные вопросы по поводу отдельных тонкостей, чем просить заново всё объяснить.

    Краткие ответы:

    1) 2^25 - это количество всех возможных способов бросать камни в пруд (Daniel Burdakov выше показал, почему именно столько). Соответственно, раз мы теоретически можем закодировать столько вариантов, то для максимально возможного N верно N*N <= 2^25. Ну а так как N - натуральное число, то там мы получаем оценку на N.

    2) 5792 - это и есть максимальное теоретически возможное N, выше которого заведомо невозможно прыгнуть. Если Вам не ясно, как получены какие-то из этих чисел, то поясните, что именно не можете понять.

    3) 1716 - это максимальное N, которое смог закодировать vayun. Он кратко объяснил, как сделал это. Мне кажется, что его ход мысли вполне естественен. Что именно надо пояснить подробнее в его идее? Я буду рад рассказать, но сперва задайте вопрос.

    Максимально полно использовать предыдущие шаги - это хорошая идея. Именно так и можно увеличивать N.

    ОтветитьУдалить
  15. Анонимный28.12.2011, 11:03

    Конкретный вопрос такой. Как описанным алгоритмом первый скажет "1658", а второй "118". Быть может на примере станет понятно. Если пример неудачный и не раскрывает сути, дайте на другом примере.

    ОтветитьУдалить
  16. Анонимный28.12.2011, 11:12

    Если по описанию алгоритма нужны вопросы, то пожалуйста.

    Прозвучало "Всего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), ..."

    Непонятно каким образом можно делать либо не делать смену хода (и что такое вообще смена хода), если ранее прозвучало что оба должны ходить ПООЧЕРЕДИ. Соответственно, если все остальные выкладки базируются на этом то и они автоматически непонятны.

    ОтветитьУдалить
  17. Анонимный28.12.2011, 11:20

    У меня вопрос собственно не в том как цифры вывели, я это и сам смогу как только осознаю суть алгоритма. Извините что неправильно изначально сформулировал.

    ОтветитьУдалить
  18. Уважаемый аноним, конкретный пример рассматривать не очень интересно, так как писанины много будет, а смысла мало. Давайте попробуем вникнуть в алгоритмы:

    1) Фраза "Всего возможных _ситуаций_ 2^25 (в каждом из 25 междукамней можно сделать либо не сделать смену хода), ..." надо понимать следующим образом. Бросать группу камней можно так:
    - получив ход, игрок бросает один камень (так как он обязан бросить положительное число камней),
    - а после этого он несколько раз принимает решение, бросить ещё один камень или передать ход партнёру.
    Выходит, после каждого камня могут быть два исхода, поэтому за 25 бросков (после первого, который можно сделать только одним способом) могут возникнуть 2^25 вариантов.

    Т.е. по условию игроки поочерёдно бросают группы камней (непустые). Но это же можно описать как "игроки бросают камни один за другим, иногда передавай ход друг другу". И такое описание более удобно для подсчёта всех возможных способов бросить камни.

    2) Что касается идеи решения vayun, то я всё ещё не знаю, что здесь стоит прокомментировать. Вроде бы достаточно ясно изложено. Конечно, можно расписать и подробнее, но я не хотел бы это делать по всему тексту, а предпочёл бы ограничиться пояснениями только к непонятным Вам фрагментам. Поэтому жду конкретных вопросов.

    ОтветитьУдалить
  19. Анонимный28.12.2011, 12:58

    1. Вот теперь стало понятно, спасибо. Проще наверно так: Если ходом первого собеседника сказать "1", а ходом второго сказать "0", то всего возможно 2^25 различных фраз, состоящих из "1" и "0", длиной 26. Почему в 25 а не в 26 степени - потомучто фраза всегда начинается с "1" по условию. "Первый собеседник" и "второй собеседник" здесь означают "тот кто начал говорить первым" и "тот кто начал говорить вторым"

    Но я здесь не согласен с тем, что первым должен начинать говорить всегда "первый" собеседник. Если ввести вариацию - кто первым начинает вести диалог, то можно сообщить дополнительный бит информации, если вести речь о теоретическом пределе, хотя технически это наверно очень сложно, если вообще возможно.

    ОтветитьУдалить
  20. Уважаемый аноним, Вы правы,
    если разведчики заранее договорились, в каких ситуациях первый подходит к камням, а в каких второй, то можно упаковать ещё чуть-чуть информации. Это важный, но достаточно тонкий момент.

    ОтветитьУдалить
  21. С переходм хода всё же не очень понятно. Если он добровольный, то это можно осуществить либо паузой, либо жестом. Других вариантов я не вижу. Но тогда возможен и бросок в ноль камней. :)
    Если нет, то имеется скорее обрыв счёта - он бросил камень, когда я бросил уже два.

    ОтветитьУдалить
  22. Анонимный29.12.2011, 6:46

    Дада, я тоже это увидел. Каким образом второй собеседник понимает что уже его очередь ходить? Допустим это некий жест от первого собеседника либо слишком длинная пауза между бросками.

    Но тогда сразу же напрашивается вывод, что помимо "1" и "0", в тексте могут быть символы "p" - пасс. Т.е. кроме такого сообщения
    101100010 возможно и такое
    1p11000p0
    а это резко увеличивает объем передаваемой информации.

    ОтветитьУдалить
  23. sans17 и аноним, никаких пауз и жестов.
    Подошёл к кучке камней, набрал в руку несколько штук, бросил их в пруд, отошёл. После этого ход перешёл ко второму разведчику, если камни в кучке ещё остались.

    Эта ситуация полностью эквивалентна следующей:
    подошёл к доске, написал на ней положительное целое число так, чтобы сумма всех записанных чисел не превзошла 26, отошёл, тем самым передав ход.

    ОтветитьУдалить
  24. Дмитрий К.29.12.2011, 11:30

    Илья, Вы пишете:

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

    Важность момента несомненна, но пока что больше беспокоит его тонкость. Одно дело, если они заренее договорились, что первым подходит конкретно Вася. При более сложных договоренностях, при встрече должна состояться какая-то процедура выбора первого, а следовательно, передача информации каким-то способом, не включающим кидание камней. Не противоречит ли это условию задачи?

    Если возможно достаточно легитимно провести такую процедуру выбора первого, то 2508 реально.

    ОтветитьУдалить
  25. Ну так подход к кучке (отход) и есть жест.
    Второй разведчик подходи к кучке, и сразу же отходит - типа передумал.

    ОтветитьУдалить
  26. Анонимный29.12.2011, 19:25

    sans17, сто раз же уже сказали, что бросают камни поочерёдно: сначала один бросил сколько-то, потом второй, потом опять первый, потом опять второй. И в условии это написано, и в комментарии много раз разжевали. Нельзя получить ход, но потом ничего не бросить. Всегда надо бросить хотя бы один камень, а потом передать ход. Что непонятного-то?

    ОтветитьУдалить
  27. 2535: https://plus.google.com/u/0/116477975871185858002/posts/NehYW4KSbs6

    ОтветитьУдалить
  28. Дмитрий К.30.12.2011, 10:29

    Мне думается, что все-таки возможно согласовать право первого хода, не нарушая правил. Они могли договориться, кто из них первым приближается к камням. При этом он может сразу начать бросать камни, либо дожидаться, когда приблизится второй и сделает свой первый ход. Во всяком случае, со стороны это будет выглядеть именно так, как описано в условии - сначала один кинул, затем другой, и так далее, не нарушая очередности.

    При таком подходе, максимум, что пока удалось выжать - это 2683.

    ОтветитьУдалить
  29. Анонимный30.12.2011, 17:56

    Подошел, отошел, попрыгал на одной ноге. Это все не соответствует задумке условия.

    Это разведчики, им вообще не обязательно видеться. Они могут приезжать на берег реки и кидать камни из заранее заготовленной кучи с интервалом от дней до месяцев. Как в таком случае определить, что первый "подошел, но не стал сразу кидать"?

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

    ОтветитьУдалить
  30. Вот она разница.
    Если 1716 можно понять и оценить в уме, то чтобы проверить 2535 надо смотреть на программу.
    Следующий этап - задача настолько закрученная, что нужна программа проверяющая правильность алгоритма?

    ОтветитьУдалить
  31. Дмитрий К.30.12.2011, 23:31

    Уважаемый Аноним,

    В условии задачи сказано: "Согласовав заранее свои действия, они встретились на берегу реки". Впрочем, Вы предлагаете тоже вполне интересную модификацию задачи. При такой постановке я достиг 2092.

    Собственно, основную идею решения озвучил vayun. Количество бросков можно увеличить и до 9, и до 10 (на 11 уже камней не хватает). В тех случаях, когда первый делает ход за второго, ему необязательно выбрасывать сразу все оставшиеся камни. Он кидает один камень, а второй разведчик уже сам докидывает остальные камни текущего хода. Только тут уже разбиения не совсем произвольные. При разбиении на 9 частей, 8-я часть должна содержать не менее двух камней. А при разбиении на 10 - и 8-я, и 9-я.

    Sophist, а Вы расскажете, как достигли 4718?

    ОтветитьУдалить
  32. Анонимный09.01.2012, 22:48

    Задачка замечательная. Для 1700 хватает и 25 камней, а 26 хватает максимально на 2526 значений 2-х шифров. Число 1700 - частный случай, общий - когда первому надо передать одно из "а" чисел, второму - одно из "в" чисел. Считается рекурсивно -

    Ясно, что К(1,1)=0.

    В случае (1,в) первый кидает один камень - чтобы передать ход второму. Значит, К(1,с)=1+К(с,1).

    Хитрее, когда а>1. Число а можно по-разному представить в виде суммы натуральных слагаемых, а=а1+а2+а3... Для каждого такого разбиения есть максимум среди 1+К(в,а1),2+К(в,а2),3+К(в,а3)... - и нужно выбрать разбиение, минимизирующее такой максимум. Ну и здесь нужно исхитриться обойтись без перебора ;)
    nik_vic из ЖЖ.

    ОтветитьУдалить
  33. Анонимный10.01.2012, 9:00

    В предположении, что один участник, после того как у другого уже кончились камни, может несколько раз подряд вставать со скамейки, подходить к кучке, делать броски, возвращаться назад на скамейку, получается сказать обоим любое число в диапазоне от 1 до 8191.

    Это соответствует тому, что если на доске идут подряд числа и первые несколько нечетных чисел составляют сумму 13, то все остальные числа считаются четными и тоже составляют сумму 13, и наоборот с точностью до слов "четное", "нечетное".

    По-моему данное предположение не противоречит условию задачи, поправьте если не так.

    ОтветитьУдалить
  34. Уважаемый аноним,
    это предположение противоречит условию (ведь каждый должен бросить хотя бы один камень перед тем, как передаст ход партнёру).

    Да и вообще, что значит "у одного уже кончились камни", а "второй ещё бросает". Кучка-то одна. Поэтому, если в ней что-то есть, то очередной игрок должен что-то бросить (перед передачей хода). А если в ней уже ничего нет, то игра закончилась.

    nik_vic,
    можете подробнее расписать вычисления для случая a>1? (речь о том, как именно там можно исхитриться) Думаю, многим было бы интересно.

    Sophist,
    было бы интересно увидеть пояснения к Вашему решению.

    ОтветитьУдалить
  35. Кто-нибудь сможет привести формальное описание методики обмена? Алгоритм или код на С, Pascal или VB?
    Ни в одном описании решения не удалось разобраться.

    ОтветитьУдалить
  36. Дмитрий К.11.01.2012, 15:29

    chukchatel,

    Вот, например. Сначала, для простоты, без оптимизации:

    1. Каждый из разведчиков (назовем их А и В) представляет число 13 в виде суммы 6, 7 или 8 ненулевых слагаемых. Таких представлений 792+924+792=2508.

    2. А подходит к куче камней. Если у него 7 или 8 ходов, он сразу делает свой первый ход. Иначе просто стоит. Поскольку еще не было ни одного броска, это не будет являться пустой передачей хода.

    3. Подходит B. По количеству камней в куче определяет, сделал ли A ход, и если да, то какой именно. B делает свой первый ход.

    4. Далее они бросают по очереди.

    5. Если количество ходов у них оказалось одинаковым, то это очевидный случай.

    6. Если у X (тот, кто бросал первым) ходов на один больше, чем у Y (который бросал вторым), то это тоже очевидный случай.

    7. Если у X на два хода больше, то это 6 и 8. Тогда X делает свой 7-й ход, а 8-й за него делает Y, т.к. ситуация уже однозначна.

    8. Если у Y на один ход больше, то это 7 и 8 (в силу правила 2). В этом случае Y сам делает свой 7-й ход, а 8-й за него делает X.

    9. На два хода больше у Y быть не может.

    Таким образом достигается 2508. Но можно немного оптимизировать. Разбиение производится на 6, 7, 8, 9 или 10 ходов. В случае 9 ходов, 8-й состоит из не менее двух камней. В случае 10 - и 8-й, и 9-й, оба не менее двух. Тогда тот, кому приходится делать чужой ход, бросает один камень, а его коллега завершает свой ход. На последний ход можно оставлять и один камень, т.к. уже не возникнет неопределенности.

    Так получается 2683. Этот результат мне пока улучшить не удается.

    ОтветитьУдалить
    Ответы
    1. Полагаю, многим этот комментарий будет очень полезен. Благодарю, что нашли силы и время на него!

      Удалить
    2. Анонимный03.04.2012, 13:07

      А как влияет число камней у какого-то из игроков на количество слагаемых, которые они выбирают для представления числа 13?

      Удалить
  37. Дмитрий К., спасибо за разъяснения.

    ОтветитьУдалить
  38. Анонимный12.01.2012, 14:25

    Как я понимаю такой алгоритм не противоречит условию первой (оригинальной) задачи про шпионов:
    Кинул левой рукой=0, кинул правой рукой =1. Если у каждого по 13 камней бинарное кодирование дает 2^13=8192. Для второй задачи (про цифры на доске) очевидно не совсем подходит.
    С уважением Андрей.

    ОтветитьУдалить
  39. Уважаемый Андрей,
    это не две разных задачи, а одна задача, которую можно сформулировать разными способами (кому как удобнее). Конечно, все эти игры в кидание разными руками, подмигивание глазами, метание камней на разные расстояния (или в разные секторы пруда) не могут быть интересны, так как позволяют совсем маленьким усилием головы достичь якобы больших результатов.

    ОтветитьУдалить
  40. Анонимный12.01.2012, 14:50

    ... Сейчас посмотрел на доску в кабинете, она вся она исписана маркерами 4-х различных цветов...
    Если каждый из участников 13 раз напишет число 1 различными цветами маркера, то 4^13=67108864
    С уважением Андрей.
    PS:
    Пришел как-то в Комитет по науке Государственной думы РФ человек с разработкой супероружия. Предъявляет официальную бумагу, что он направлен ФСБ. Комитет, конечно, был жутко заинтригован. Спрашивают, а где чертежи? Тот удивляется: а зачем? Я, говорит, изобрел красную кнопку. Ее нажимаешь - и все ядерное оружие противника взрывается. Его спрашивают: а как это сделать? Гость, подбоченясь, изрекает: «Я вам принес идею. А ваша задача - ее реализовать»

    ОтветитьУдалить
  41. Анонимный12.01.2012, 15:16

    nik_vic ЖЖ
    ==Дмитрий К.Jan 11, 2012 03:29
    ==Если у него 7 или 8 ходов, он сразу делает свой первый ход. Иначе просто стоит.==
    Гм, и что мешает каждому из них стоять по 9999 раз? Около 2-х камней ;)

    ОтветитьУдалить
  42. Дмитрий К.12.01.2012, 15:33

    nik_vic ЖЖ:
    Гм, и что мешает каждому из них стоять по 9999 раз? Около 2-х камней ;)

    Нацеленность на результат ;)

    Или Вы имели в виду, как это отражено в алгоритме? См. п.3: B делает свой первый ход. Безусловно. А также п.4: Далее они бросают по очереди.

    ОтветитьУдалить
  43. Анонимный12.01.2012, 15:45

    Дмитрий К.Jan 12, 2012 03:33 AM
    nik_vic ЖЖ:
    Вы решаете другую задачу. В оригинале первый непременно бросает хоть один камень (не имеет права написать на доске 0 или пустое слово).

    ОтветитьУдалить
  44. Дмитрий К.12.01.2012, 16:11

    В оригинальном условии никак не оговаривается такое требование, чтобы первым кидал именно тот, кто первым подошел. По формулировке условия, "первым" называется тот, кто первым кинул камни. Вот чего действительно нельзя - это не бросить хотя бы один камень после того, как другой бросил. Ну естественно, если еще камни остаются.

    ОтветитьУдалить
  45. Анонимный12.01.2012, 17:37

    == Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять...==

    ОтветитьУдалить
  46. Дмитрий К.12.01.2012, 18:26

    == Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять...==

    Ну да, Вы абсолютно правильно цитируете. Вот тот, который первым кинул - это и есть первый. А другой - это второй. Но подойти он мог и раньше.

    Вот представьте себе, что Вы за ними наблюдаете - осуществляете надзор за соблюдением процедуры. Вот подошел один и стоит. Потом подходит другой и бросает камни. Дальше по очереди. Какое нарушение Вы сможете им вменить? Заметьте, они заранее согласовывают свои действия между собой, но не с Вами и не с кем-либо еще. Они совершенно запросто Вам ответят, что именно так они и договорились - первым бросает именно этот. Просто он немного опоздал (в пробке застрял).

    Или возможно такое согласование действий. Разведчик B подходит ровно в 12:00 и делает свой ход. А разведчик A, по ситуации, подходит либо в 11:59 либо в 12:01. В 12:00 B видит либо 26 камней, либо меньше.

    ОтветитьУдалить
  47. Анонимный12.01.2012, 18:36

    "Изюминка" исходной формулировки в том, что они не имеют права встречаться. Петров обязан 1-го апреля (далее - по нечётным) выкинуть несколько камней, Иванов делает то же по чётным дням.

    ОтветитьУдалить
  48. Дмитрий К.12.01.2012, 18:46

    "Изюминка" исходной формулировки в том, что они не имеют права встречаться.

    Э-э-э... А мы точно одну и ту же исходную формулировку обсуждаем?

    "Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней."

    ОтветитьУдалить
  49. Дмитрий К,
    мне тоже кажется, что они вполне могли договориться, что Андрей приходит первого или третьего апреля, а Борис заведомо второго. Т.е. Андрей принимает решение будет он первым или вторым. Процедуру это не нарушает (так как абстрактный проверяющий не знает заранее, кто первый, а кто второй).
    Встретились они на берегу или нет - это уже не так важно, так как не влияет на решение.

    В то же время, я согласен, что имеет смысл и другая версия этой задачи: Андрей всегда бросает камни первым, а Борис - вторым. Этот вариант проще, поэтому начинать решать задачу стоит именно с него. Но потом, конечно, интересно разобраться и с более заковыристым.

    ОтветитьУдалить
  50. Анонимный13.01.2012, 12:22

    == Т.е. Андрей принимает решение будет он первым или вторым. Процедуру это не нарушает ===
    Дело не в том, кто первый - это должно быть определено в "задании". Дело в появлении права подойти к доске и написать в качестве очередного слагаемого ноль.

    nik_vic ЖЖ

    ОтветитьУдалить
  51. > Дело в появлении права подойти к доске и написать в качестве очередного слагаемого ноль.
    Вроде бы уже несколько раз обсуждали, что нет такого права.

    ОтветитьУдалить
  52. Дмитрий К.13.01.2012, 19:21

    Согласен с тем, что условие встречи - не принципиальное. Также согласен с тем, что и альтернативные постановки задачи имеют полное право на жизнь. В частности, и с таким условием: кто первым подошел (а это как повезет), тому первому и ходить. Для такого случая могу предложить решение, совершенно аналогичное приведенному ранее.

    13 камней делятся на от 6 до 10 ходов. Для 6 и 7 ходов разбиения произвольные (уже разобрано выше, это дает 1716). Если ходов больше 7, то с 7 по предпоследний включительно содержат не менее двух камней. Способ взаимодействия такой же, как описано выше. Это дает дополнительно 376. Получается 2092.

    Этот алгоритм вполне годится и в том случае, когда выбор первого бросающего фиксирован. Но в таком случае у меня есть смутное подозрение, что можно и в алгоритм внести некоторую асимметрию, при этом немного улучшив результат. Но конструктивного решения по этому поводу у меня нет.

    ОтветитьУдалить
  53. Анонимный13.01.2012, 22:29

    == можно и в алгоритм внести некоторую асимметрию, при этом немного улучшив результат==
    Попробуйте передать 23х23 кода, располагая 12-ю камнями.

    nik_vic ЖЖ

    ОтветитьУдалить
  54. Дмитрий К., Илья Весенний,
    прошу прощения, что сразу не ответил.

    Сейчас уже, если честно, не могу привести точные расчеты.

    Но рассуждал я так. Я вспомнил другую задачу, про два яйца и многоэтажную башню.

    А именно: есть два одинаковых яйца, которые разбиваются, будучи брошенными с определенного этажа и выше. Нужно найти номер этого этажа, минимизировав число бросаний.

    Если бы яйцо было одно, его бы оставалось только бросать по очереди с каждого этажа снизу вверх. С двумя яйцами интереснее.

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

    Но оказалось, что это не самый оптимальный вариант. Его можно улучшить, варьируя интервал бросания первого яйца в зависимости от того, сколько попыток уже было потрачено. (Для 100 этажей суммарное число бросаний не больше 14: первое бросание первого яйца -- с 14-го этажа, второе -- с 14+13=27-го, третье -- с 27+12=39-го и так далее. Каждый раз остается ровно такой интервал, чтобы его можно было добить вторым яйцом за оставшееся число бросаний).

    Так вот, мне и подумалось, что таким образом можно кодировать информацию. Номеру этажа можно поставить в соответствие пару чисел -- номера этажей, на которых разбилось первое и второе яйцо соответственно.

    Дальше совершенно естественно выйти за рамки двух яиц и кодировать несколькими. Опять-таки, уже ничего не помню, но я составил программку на Python'е и выяснил, что для данной задачи (с камнями, отображая их на яйца :)) оптимальное число яиц -- шесть или семь, и при каждом из них максимальное число этажей -- 4718. (При большем числе яиц для них начинает не хватать попыток).

    Итак, каждому шпиону/разведчику отводится по 13 камней (которые соответствуют попыткам бросания яиц). За шесть ходов он передает шесть чисел, каждое из которых соответствует номеру попытки, с которой разбилось n-ное яйцо. По этим данным можно восстановить номер критического для яиц этажа (= передать число в пределах общего числа этажей).

    Вот. :)

    ОтветитьУдалить
    Ответы
    1. Спасибо, что нашли время так подробно описать ход мысли. Последние годы мне гораздо интереснее понять, как человек шёл к решению, чем увидеть ответ :)

      Удалить
  55. Анонимный16.01.2012, 21:11

    nik_vic ЖЖ
    ==== Вот вариант для Экселя без оптимизации представления таблицы и других мелочей и визуализацией для малых NN.

    =========================
    Const NN = 256
    Dim K(1 To NN, 1 To NN) As Byte
    Sub sifr()
    For a = 1 To NN: For b = 1 To NN: K(a, b) = 99: Next b, a: K(1, 1) = 0
    For d = 3 To 2 * NN 'по диагоналям
    For b = 1 To NN: a = d - b: If a <= NN And a > 0 Then K(a, b) = Ff(a, b) 'внутри квадрата
    Next b
    Next d

    For y = 1 To NN: For x = 1 To NN: Cells(y, x) = K(y, x): Next x, y
    End Sub
    Function Ff(a, b) As Byte
    If a = 1 Then Ff = K(b, 1) + 1: Exit Function
    h1 = K(a - 1, b) 'pristrelka
    AAA: h = h1: s = 0
    For x = a - 1 To 1 Step -1
    If K(b, x) < K(b, x + 1) And h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
    Next x
    If s >= a Then Ff = h1 Else h1 = h1 + 1: GoTo AAA
    End Function

    ОтветитьУдалить
  56. Анонимный17.01.2012, 14:10

    А вот так быстрее. Результат - 2535.
    ==============
    Const NN = 2555
    Dim K(1 To NN, 1 To NN) As Byte
    Sub sifr(): 'Dim a As Integer, b As Integer, d As Integer
    For a = 1 To NN: For b = 1 To NN: K(a, b) = 99: Next b, a: K(1, 1) = 0
    For d = 3 To 2 * NN 'diagonl'
    Cells(1, 2) = d 'chtobi videt' stadiu
    For b = 1 To NN
    a = d - b
    If a > NN Then GoTo Nextb 'vne кvadrata
    If a < 1 Then GoTo Nextb 'vne кvadrata
    If K(a, b) < 99 Then GoTo Nextb 'ужe soschitano
    Call Ff(a, b)
    Nextb: Next b
    Next d
    For y = 1 To NN: Cells(y, 1) = K(y, y): Next y 'raspechatka
    End Sub
    Sub Ff(a, b)
    If a = 1 Then K(a, b) = K(b, a) + 1: Exit Sub
    h1 = K(a - 1, b) 'pristrelka
    AAA: h = h1: s = 0
    For x = a - 1 To 1 Step -1
    If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
    Next x
    If s < a Then h1 = h1 + 1: GoTo AAA
    If s > NN Then s = NN
    For i = a To s: K(i, b) = h1: Next i
    End Sub
    ======================
    НикВик

    ОтветитьУдалить
    Ответы
    1. Анонимный22.01.2012, 16:12

      А-а, не понимаю, почему именно так! :-(
      Какая логика? Что вообще делает этот код? Почему именно это?

      Удалить
  57. Дмитрий К.22.01.2012, 21:27

    А можно вот еще как подойти к решению этой задачи.

    Сначала рассмотрим как подзадачу одностороннюю передачу кода. Условимся так, что Андрей бросает первым, при этом он должен передать код, а Борис принимает код, при этом ассистируя: бросает по одному камню между ходами Андрея. Имея k камней, можно передать значение T(k). Очевидно, T(0)=T(1)=1. Несложно доказать, что T(k)=Ф[k] (число Фибоначчи).

    Применительно к нашей задаче, нас интересует Ф[17]=2584 (итоговый ответ будет поменьше).

    Еще одна подзадача - двусторонняя передача неодинаковых значений. Пусть камней k1+k2 (имеется в виду, что Андрей стремится передать значение Ф[k1]). Обменяться значениями Ф[k1] и Ф[k2] можно очевидным образом. Но хочется побольше принять взамен с минимальными потерями. Андрей отказывается применять ход, которым выбрасывается сразу k1 камней. Тогда Борис обязательно бросит один из тех k1 камней. К нему он может присоединить один или ни одного из k2 камней. К моменту, когда число Андрея будет полностью передано, у Бориса останется от 0 до k2 камней. Соответственно, Андрей сможет принять от Бориса
    sum[i=0..k2](Ф[i])=Ф[k2+2]-1 возможных значений.

    Возвращаемся к нашей задаче. Каждый ход несет в себе информацию. И чем больше камней в броске, тем меньше должен быть диапазон соответствующих ему значений, чтобы было реально передать его оставшимися камнями. Каким может быть максимальный первый ход? Если бросить 9 камней, то останется 26-9=17. Этого достаточно, чтобы передать 2584, при этом не принимая информации. Значит, первому ходу 9 соответствует некоторое единственное значение. Если бросить 8 камней, то останется 18 и можно будет в ответ передать 2583, приняв 2. 7 - соответственно 2583 и 4.

    Продолжение следует

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.22.01.2012, 22:42

      Поправка: К тому одному из k1 камней Борис может присоединить любое (в т.ч. нулевое) количество камней из числа k2.

      Удалить
    2. Дмитрий К.23.01.2012, 8:25

      Еще одну неточность заметил. Чтобы принять Ф[k2+2]-1 значений, надо отказаться не только от хода в k1 камней, но и (k1-1) за один раз. Т.е. цена вопроса - минус 2 передаваемых значения. Но это несущественно, т.к. максимальные итоговые потери все равно больше.

      Удалить
  58. Дмитрий К.22.01.2012, 22:38

    Итак, первый ход может содержать от 1 до 9 камней. Каждому варианту сопоставим диапазон значений D[i]=Ф[2*[n-i]]. Т.е. D[9]=Ф[0]=1, D[8]=Ф[2]=2, ..., D[1]=Ф[16]=1597. В сумме Ф[17]. Легко видеть, что если первый ход одного из участников окажется 9,8 или 7 камней, то граница Ф[17]-1 достигается. Если же, например, Андрей сделает первый ход 6 камней, то камней останется 20, а передать еще останется D[6]=Ф[6]=13. Борис же, исходя из 17+3 камней, может принять только Ф[5]-1=7, передав свои 2583. С потерей в 6 единиц еще можно мириться (в смысле, пойти на то, что итоговый ответ будет на 6 меньше), но чем дальше, тем больше. В случае хода в один камень при такой стратегии потери уже слишком большие.

    Но тогда мы применим такой прием. После того, как первый ход сделан, массив D пересчитывается, исходя из текущей ситуации. Например, если Андрей первым ходом бросил один камень, то на следующий ход его массив D может состоять уже из 8 элементов, т.к. ему остается передать одно из Ф[16] значений. В этом случае массив заполняется числами Фибоначчи с нечетными номерами от 1 до 15, что в сумме дает Ф[16]-1. Еще одна системная потеря.

    Попробуем прикинуть, сколько мы можем в итоге потерять от значения Ф[17]. При благоприятном ходе (достаточно много камней), остаточный обмен происходит с потерей максимум единицы, и игра заканчивается. А иначе мы пересчитываем D. Максимальное количество раз пересчета массива D - в том случае, если они будут все время ходить по одному камню. Больше 13 раз это невозможно. А больше 12 не нужно. А пожалуй, что и больше 10 не нужно, т.к. для 6 камней уже все достаточно очевидно. Но ведь при этом будут чередоваться четные и нечетные номера соответствующих чисел Фибоначчи (а сумма чисел с четными номерами равна в точности следующему). Получается, что больше 6 единиц потерять не должны. Выходит 2577.

    ОтветитьУдалить
  59. Дмитрий К.23.01.2012, 8:38

    А пожалуй, что от второй подзадачи (с k1+k2 камнями) можно и вовсе отказаться. Решение станет красивее. Если один из игроков делает максимальный ход, то второй применяет алгоритм односторонней передачи. В противном случае, по результатам пары ходов (А+Б) каждый пересчитывает свой массив D.

    ОтветитьУдалить
    Ответы
    1. Дмитрий К,
      спасибо за такое подробное описание!
      Я уверен, многим будет интересно его прочитать.

      Удалить
  60. Анонимный23.01.2012, 20:28

    nik_vic ЖЖ
    Дмитрий К ==Выходит 2577==
    Многовато...
    Попробуйте с Вашими идеями получить 23х23 для 12 камней или 31х31 для 13 камней.
    http://www.ljplus.ru/img4/n/i/nik_vic/Shifr13-13.GIF

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.23.01.2012, 21:37

      Ну конечно, я мог где-то и ошибиться. В процессе размышлений не раз ловил себя на ошибках. Если заметите ошибку - сообщите, пожалуйста.

      А что в Вашей таблице означают красные числа?

      Попробую. А скажите сразу, у Вас это получилось?

      Удалить
  61. Анонимный23.01.2012, 21:49

    nik_vic ЖЖ
    Красные - на диагонали, в максимальном положении для данного количества камней.
    Вот главная часть программы -
    =====
    h1 = K(a - 1, b) 'pristrelka
    AAA: h = h1: s = 0
    For x = a - 1 To 1 Step -1
    If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
    Next x
    If s < a Then h1 = h1 + 1: GoTo AAA
    If s > NN Then s = NN
    For i = a To s: K(i, b) = h1: Next i
    =====

    ОтветитьУдалить
  62. Дмитрий К.25.01.2012, 8:13

    В самом деле, многовато получилось. Нашел-таки у себя ошибку. Не всегда корректен такой способ пересчета массива D. Надо найти какой-то более корректный вариант. Соответственно, результат окажется поскромнее. Но вроде бы, не должно быть намного.

    А вот 23х23 для 12 камней - это, на мой взгляд, многовато. Поэтому и спрашиваю, получилось ли это у Вас. Не рассчитать количество (в чем можно и ошибиться), а именно указать, как каждый из участников зашифрует свое значение и как расшифрует значение партнера.

    ОтветитьУдалить
  63. Анонимный25.01.2012, 11:36

    nik_vic ЖЖ

    Дмитрий К.==А вот 23х23 для 12 камней - это, на мой взгляд, многовато.==

    12 камней хватает даже для 24х23 - смотрите мою таблицу, строка 23.
    Первое разбиение - 24=13+7+3+1, бросается 1, 2, 3 либо 4 камня.

    ОтветитьУдалить
  64. Дмитрий К.31.01.2012, 14:20

    А вот немножко оптимизированный вариант. И заодно уж, наряду с таблицей K, заполняется и таблица P, содержащая правила разбиения для каждого ключа. При практическом применении такой таблицей пользоваться удобнее.

    var N = 32; // максимальный ключ
    var pebblesLimit = 12; // не считать больше, чем интересует

    var fibCount;
    var fib = new Array();
    calcFib();

    function calcFib()
    {
    fib[1] = fib[0] = 1; fibCount = 2;
    do fib[fibCount] = fib[fibCount-2] + fib[fibCount-1]; while (fib[fibCount++] < N);
    }

    var K = new Array(); for (var i = 0; i < N; i++) { K[i] = new Array(); }
    var rFilled = new Array(), rFilling = new Array(), cFilled = new Array();
    rFilled[0] = cFilled[0] = 1;
    for (var i = 1; i < N; i++) rFilled[i] = cFilled[i] = 0;

    var P = new Array(); for (var i = 0; i < N; i++) { P[i] = new Array(); }
    var pFilled = new Array();
    P[0][0] = 1; pFilled[0] = 1;
    for (var i = 1; i < N; i++) pFilled[i] = 0;

    var cCompleted = 0;

    calcPebbles();

    function calcPebbles()
    {
    var currPebbles = 2;

    while ((currPebbles <= pebblesLimit) && (cCompleted < N))
    {
    var n = currPebbles < fibCount ? fib[currPebbles-1] : N;
    for (var c = cCompleted; c < n; c++) rFilling[c] = 0;
    for (var c = cCompleted; c < n; c++)
    {
    var r = cFilled[c];

    var count = c == 0 ? fib[currPebbles-2] : rFilled[c]-rFilling[c];

    var x = r+count;
    if (x <= N) P[c][pFilled[c]++] = count;
    if (x >= N) cCompleted++;

    cFilled[c] += count;
    while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }
    }
    currPebbles++;
    }
    }

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.31.01.2012, 15:32

      Для визуализации создал pebbles.html:

      <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

      <html xmlns="http://www.w3.org/1999/xhtml">
      <head>
      <title>pebbles</title>
      <style type="text/css">
      table { margin-top: 2mm; border-collapse: collapse; }
      td { border: solid 1px black; text-align: center; }
      td.key { font-weight: bold; background-color: #cccccc; padding-left: 0.5ex; padding-right: 0.5ex; }
      td.diag { color: #aa0000; font-weight: bold; }
      td.count { width: 3ex; }
      td.portion { width: 6ex; border: none; }
      </style>
      </head>

      <script type="text/javascript" src="pebbles.js"></script>

      <body onload="showK(); showP();">

      </body>
      </html>


      Функции showK и showP включил в pebbles.js:

      var viewportOrig = 0, viewportSize = 34;

      function showK()
      {
      var tbl = document.createElement("table");
      tbl.cellSpacing = 0;
      document.getElementsByTagName("body")[0].appendChild(tbl);
      var tbd = document.createElement("tbody");
      tbl.appendChild(tbd);

      var tr = document.createElement("tr");
      tbd.appendChild(tr);
      for (var i = 0; i <= viewportSize; i++)
      {
      var td = document.createElement("td");
      tr.appendChild(td);
      td.className = "key";
      td.innerHTML = i == 0 ? " " : viewportOrig + i;
      }

      for (var i = 0; i < viewportSize; i++)
      {
      var r = viewportOrig + i;

      tr = document.createElement("tr");
      tbd.appendChild(tr);

      var td = document.createElement("td");
      td.className = "key";
      tr.appendChild(td);
      td.innerHTML = r+1;

      for (var j = 0; j < viewportSize; j++)
      {
      td = document.createElement("td");
      td.className = "count";
      if (j == i) td.className += " diag";
      tr.appendChild(td);
      var c = viewportOrig + j;
      td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";
      }
      }
      }

      function showP()
      {
      var tbl = document.createElement("table");
      tbl.cellSpacing = 0;
      document.getElementsByTagName("body")[0].appendChild(tbl);
      var tbd = document.createElement("tbody");
      tbl.appendChild(tbd);

      for (var i = 0; i < viewportSize; i++)
      {
      var r = viewportOrig + i;
      if (r >= N) break;

      tr = document.createElement("tr");
      tbd.appendChild(tr);

      var td = document.createElement("td");
      td.className = "key";
      tr.appendChild(td);
      td.innerHTML = r+1;

      for (var j = 0; j < P[r].length; j++)
      {
      td = document.createElement("td");
      td.className = "portion";
      tr.appendChild(td);
      td.innerHTML = P[r][j];
      }
      }
      }

      Удалить
  65. Анонимный31.01.2012, 18:45

    nik_vic ЖЖ

    Дмитрий К.==А вот немножко оптимизированный вариант.==
    А в чём оптимизация?
    Ваш pebbles.html не пошёл, пытаюсь разобраться...

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.31.01.2012, 19:11

      Ну не знаю... Я вот только что прямо отсюда на другой компьютер скопировал. И прекрасно сразу все пошло. Жаль только, что при вставке сюда программного кода форматирование пропало, это пришлось вручную восстанавливать, а то некрасиво. Надо в одну директорию поместить файлы pebbles.html и pebbles.js (здесь приведен в двух фрагментах).

      А оптимизация в том, что вся таблица заполняется одной тупой арифметикой, практически без логики - вся логика только в том, чтобы за границы не выйти. Ну и обход таблицы без повторного захода в просчитанные клетки.

      Удалить
    2. Дмитрий К., каким браузером пользуетесь?
      nik_vic, смогли разобраться?

      У меня ни в FF, ни в Chrome не заработало (т.е. выводит только шапку таблицы, а данные не отображаются). Есть идеи, как поправить?

      Удалить
    3. Дмитрий К.01.02.2012, 10:07

      Илья,

      Я запускал в IE и FF. Проблем не наблюдал. Раз выводит шапку и на этом останавливается, вероятен какой-то exception в функции showK, т.к. она должна выводить квадратную таблицу размером viewportSize. Эти границы для нее определены безусловным образом. А FF что-нибудь пишет в консоль ошибок?

      Удалить
    4. Дмитрий К,
      да, ошибка в 40 строке файла pebbles.js (не определены N и K, речь о строке «td.innerHTML = (r < N) && (c < N) ? (K[r][c] ? K[r][c] : " ") : " ";»). И я глазами тоже не вижу их объявления.

      Удалить
    5. Дмитрий К.01.02.2012, 11:12

      40? Понятно. Это я невнятно изложил. Файл pebbles.js начинается с предыдущего сообщения, т.е. с

      var N = 32; // максимальный ключ
      var pebblesLimit = 12; // не считать больше, чем интересует
      ...

      А в следующем сообщении, начиная с

      var viewportOrig = 0, viewportSize = 34;
      ...

      - это его продолжение

      Удалить
    6. Спасибо, теперь всё работает.

      Удалить
  66. Анонимный31.01.2012, 20:03

    nik_vic ЖЖ

    Вижу, что отдельно считается К(1,в) - фибоначчи. Зачем?
    Не вижу варианта типа моего
    For x = a - 1 To 1 Step -1
    If h > K(b, x) Then s = s + (h - K(b, x)) * x: h = K(b, x)
    Next x

    Повторного захода нет и у меня.
    И есть сильно ускоряющее (используется монотонность) -
    If s > NN Then s = NN
    For i = a To s: K(i, b) = h1: Next i

    До какого числа камней Вам удалось добраться?

    Там возможна ещё и экономия памяти - за счёт времени, разумеется.

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.31.01.2012, 20:31

      Вижу, что отдельно считается К(1,в) - фибоначчи. Зачем?

      Вернее, так считается K(a,1). Затем, что каждый последующий шаг использует результат предыдущего. Но при этом где-то же должна быть и база.

      Не вижу варианта типа моего...

      Ну да, у меня нет пристрелки.

      И есть сильно ускоряющее
      If s > NN Then s = NN
      For i = a To s: K(i, b) = h1: Next i


      А вот этому и у меня есть аналог:

      while ((count-- > 0) && (r < N)) { K[r][c] = currPebbles; ++rFilling[r]; ++rFilled[r++]; }

      До какого числа камней Вам удалось добраться?

      Так можно задавать разные значения N и pebblesLimit. Ну я подставил N=2540, pebblesLimit=27. Получил K(26,26)=2535.

      Удалить
    2. Дмитрий К.31.01.2012, 20:33

      Пардон, наоборот. K(2535,2535)=26.

      Удалить
  67. Анонимный31.01.2012, 21:12

    ==Но при этом где-то же должна быть и база==

    Дык куда ж без неё: K(1,1)=0. И хватает ;)

    Насчёт 2535 - верно.
    Настоящие комбинаторщики, небось, могут и производящую функцию сварганить...

    nik_vic ЖЖ

    ОтветитьУдалить
    Ответы
    1. Дмитрий К.31.01.2012, 21:28

      K(1,1)=0 - это да, это самая базовая база. Но если в качестве базы служит целый столбец таблицы - это весьма существенное подспорье. В результате целый внутренний цикл заменяется разностью двух значений. Таблица заполняется слоями - вот этими вот дугами, которые образуют семейства одинаковых значений. Поэтому я не вычисляю h1 - оно на единицу больше предыдущего.

      Удалить
  68. Надеюсь я не очень отстал от остальных решающих эту задачу. :-)

    Сам по себе я ленивый, и поэтому ждал когда же кто-нибудь понятно разжуёт решение для ответа 2535, вникать в код не очень-то хотелось. Не дождавшись, решил порешать сам. Получились всё те же 2535, но теперь я хоть понимаю откуда.

    Да, кстати выше предлагали дать возможность одному из шпионов выбрать кто будет ходить первым. Я считаю что этот дополнительный канал информации условию не соответствует.

    Решал так, можно сказать по индукции:

    Если осталось 0 камней:
    Тот, чья очередь кидать, может передать второму 1 различных чисел.
    Втотой первому - тоже 1 различных чисел.
    Обозначу это 1:1

    Если остался 1 камень:
    У первого только один вариант выкинуть этот камень, поэтому никакой дополнительной информации он передать не может.
    1:1

    Если осталось 2 камня:
    У игрока 2 варианта:
    1) кинуть один камень, тогда второй остаётся с одним камнем (и возможностями 1:1)
    2) кинуть два камня, тогда второй остаётся с нулём камней (1:1)
    Таким образом у игрока есть 1+1=2 способа оставить второго игрока с 1 вариантом, поэтому это ситуация 2:1

    Если осталось 3 камня:
    1) можно кинуть один камень, оставив второго в ситуации 2:1
    2) кинув 2 камня, можно оставить второго в ситуации 1:1
    2) кинув 3 камня, можно оставить второго в ситуации 1:1
    Находясь перед кучей из трёх камней игрок может либо предоставить второму возможность выбрать число из двух выкинув один камень и не передав никакой информации, это ситуация 1:2,
    Либо передать информацию кинув 1, 2 или 3 камня, но не получив ничего взамен, 3:1.
    Обращаю внимание, что хотя в последней ситуации может так оказаться что передавая информацию первый кидает 1 камень и вроде бы у второго появляется возможность тоже что-то передать, это не ситуаций 3:2, потому что мы не можем гарантировать что при любом из 3х вариантов для первого, у второго будет 2 варианта.
    Таким образом, с тремя камнями ситуации может быть две: 1:2 и 3:1.

    Ситуация с 4 камнями:
    С 4 камнями я надеюсь что всё будет понятнее.
    1) кидаем один, оставляем коллегу в ситуации 1:2 или 3:1 на выбор
    2) кидаем два, оставляем в 2:1
    3) кидаем три, оставляем в 1:1
    4) кидаем четыре, оставляем в 1:1
    Если мы хотим предоставить коллеге возможность передать одно из 3х чисел, мы кидаем один камень, это 1:3
    У нас есть два способа дать ему возможность передать один из 2х чисел (кинув два камня, и кинув один, в последнем случае у него даже избыток возможности), получается 2:2
    И самое интересное: если мы не хотим от второго игрока никакой информации, у нас есть 4 способа кинуть камень сейчас, но если мы кинем 1 камень, то позже мы можем воспользоваться ситуацией 1:2, и передать ещё один из двух вариантов. Таким образом, это 5:1.
    То есть с четырьмя камнями ситуации 5:1 2:2 1:3.

    Напоминаю, что это значит, что по предварительной договорённости с 4 камнями шпионы могут:
    * первый второму может передать число от 1 до 5, не получив информации взамен
    * каждый каждому может передать число от 1 до 2
    * первый может информацию не передавать, но принять от второго число от 1 до 3

    Допустим мы просчитали возможности для всех ситуаций с количеством камней от 0 до N:
    (пример для N=4)
    S[0] = {1:1}
    S[1] = {1:1}
    S[2] = {2:1}
    S[3] = {1:2, 3:1}
    S[4] = {1:3, 2:2, 5:1}

    Для того, чтобы посчитать возможности для N+1, мы
    для каждого d (из множества натуральных чисел :-) ) {
    sum := 0
    для каждого n из 0..N {
    ищем в S[0] пару a:b, с максимальной b, при условии что a>=d;
    sum := sum + b
    }
    добавляем в S[N+1] пару sum:d
    }

    S[5] = {1:5, 2:3, 4:2, 8:1}
    И т д.
    Из S[26] выбираем пару a:b с наибольшим min(a,b) и это оказывается 2535:2536, это и есть наш ответ.
    Для того чтобы из полученных данных построить алгоритм выбора количества камней, надо идти по нему в обратном порядке.
    Написал на джаваскрипте обратный ход алгоритма, можете поиграться:
    http://crem.dyndns-home.com/files/sponges.html (только я решал в терминах мочалок а не камней)

    ОтветитьУдалить
    Ответы
    1. http://crem.dyndns-home.com/files/sponges.html

      Перенёс ссылку в место позаметнее, чтоб те которые любят играться но не любят читать скучные тексты её не пропустили. :)

      Удалить
    2. crem,
      спасибо за такое подробное описание!
      Здорово, что Вы пояснили, каким образом думали. Ведь многим часто хочется не столько узнать ответ, сколько понять, как дойти до ответа. Поэтому Ваш текст обладает повышенной ценностью :)

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний