|
iogri
172 - 16.03.2009 - 07:33
|
блин, слетели табуляторы и стало нечитаемо :(
дублирую:
Имеем три кучки камней с количествами (Кучка1)A > (Кучка2)B > (Кучка3)C
Очевидно, что можно записать B = D + k*C (деление с остатком)
Алгоритм такой:
Представим k в двоичном виде (например [100101]). В квадратных скобках будем записывать двоичные числа
Тогда количество камней в кучках запишется так (количество в кучке 1 нас не интересует, важно, что там камней больше чем в кучке 2):
Кучка 1 Кучка 2 Кучка 3
D + [100101] * C [1] * C
Если последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1 Кучка 2 Кучка 3
D + [100100] * C [10] * C
Если пред-последний разряд в числе k = 0, то удваиваем кучку 3 за счет кучки 1:
Кучка 1 Кучка 2 Кучка 3
D + [100100] * C [100] * C
Если пред-пред-последний разряд в числе k = 1, то удваиваем кучку 3 за счет кучки 2:
Кучка 1 Кучка 2 Кучка 3
D + [100000] * C [1000] * C
И так далее…
В итоге, получим позицию:
Кучка 1 Кучка 2 Кучка 3
D + [000000] * C [1000000] * C
Итак, мы добились следующего: в кучке 2 камней стало меньше, чем было изначально в кучке 3. То есть, минимальное количество во всех трех кучках уменьшилось.
Переобозначаем кучки, чтобы прийти к ситуации (Кучка1)A > (Кучка2)B > (Кучка3)C и повторяем алгоритм.
В итоге получим, что количество в кучке 2 = 0 (после каждого применения алгоритма оно уменьшается). То есть, на предыдущем шаге мы удвоили кучку 3 за счет кучки 2. А это и было «решение задачи».
|