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

Зашла так не нароком, интересненько 

Еще в "Осторожно, конкурс" заходи:)

Есть чуть попроще задачка про шоколадку.

Аня и Боря делят прямоугольную шоколадку размером MxN. Делают дети это так: они по очереди отламывают от одного из концов шоколадки кусок квадратной формы со стороной, равной меньшей из сторон шоколадки. Если в какой-либо момент остаётся шоколадка квадратной формы, ребёнок, который должен отламывать следующим, забирает всю оставшуюся часть и процесс разделения заканчивается. Аня начинает первой.

Рассмотрим пример. Скажем, сначала у детей была шоколадка размером
6x10. Первой отламывает Аня и забирает кусок размером 6x6. Боря отламывает от оставшейся шоколадки размером 6x4 кусок размером 4x4. Остается шоколадка 2x4, от которой Аня отламывает кусок размером 2x2, и
последний кусок 2x2 Боря забирает целиком. В итоге, Ане достались куски с общей площадью 40, а Боре - с общей площадью 20.

Известна суммарная площадь кусков шоколада, доставшихся в результате
такого разделения Ане, и площадь кусков, доставшихся Боре.

Требуется найти начальные размеры шоколадки M и N, при которых доставшиеся детям площади были бы равны заданным.

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

Пусть будет какой-нибудь конкретный пример.
Допустим у Ани оказалось 31432, а у Бори - 16784. Какой был размер шоколадки.

Проверил ответ - это неверно.

[cite=(https://exper1.ruhelp.com/index.php?show … p;p=377787);SleepWalker, July 19 2014, 12:38]Раскладываем сумму чисел на простые множители, их всего 7.
Осталось рассмотреть такие разложения в произведения, для которых выполняется условие из предыдущего куплета абзаца, и для каждого посчитать. что получится.[/cite]

Ну а это собственно и есть решение. Перебрать все разложения на два множителя и проверить (для чисел до 10^9 их может быть не более 1000 - ну может быть чуть больше, не помню точно) . Единственное, что проверку нужно эффективно реализовать моделирование игры - если размер плитки _много_ на _один_, не резать квадратики по одному, а сразу скопом до остатка.

Может быть, хотя не представляю как.

Вот несколько примеров... некоторая связь конечно просматривается
126, 6 -- 11x12
88, 52 -- 7x20
120560, 62876 -- 242x758
888881111, 888881090 -- 43x41343307
965772526, 558058141 -- 21391x71237
660000050, 659999950 -- 11x120000000
904971605, 699242685 -- 29218x54905

Ясно, что при отношении взятого 1:0 будет соотношение сторон 1:1, а при 1:1 - будет 1:2. Но как это перенести на общий случай.

А вообще задача чем-то CORDIC напоминает.
Подозреваю, что решается методом последовательного приближения.

[cite=(https://exper1.ruhelp.com/index.php?show … p;p=377977);SleepWalker, July 20 2014, 05:34]Это какое-то грустное решение
Хочется чего-нибудь более эффективного.[/cite]

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

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

Там любой ход выигрышным будет (кроме отрезания полоски ширины 1).

Важно еще то, что числа SG для обеих этих частей равны 1.

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

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

Отредактировано vetal (2014-07-21 19:14:53)