Я уже так больше не могу, 7 час сижу над задачей и набрал только 62 процента максимум... Я не понимаю просто! Вроде алгоритм правильный, а решение не верное.... Просто я уже задолбался... Помогите... Я же сдохну если еще час над ней просижу... Искал где то на сайте, а там написано - "ППФФФ ЛЕГКАТНЯ ЗА 10 СТРОК КОДА РЕШИЛ :)))", ппц подавляет, мой код где то строчек 30 миниму... Просто не прошу о многом, хотя бы алгоритм... Формулу...
Слава и Оля играют в игру умножения - умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P = 1, делает умножение, затем число умножает Оля, затем Слава и т. д. Перед началом игры им задают случайное число N, и победителем считается тот, кто первым получит P >= N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.
Входные данные
В первой строке находится единственное число N. 2 <= N <= 4 294 967 295.
Выходные данные
Выводится одна строка - "Stan wins.", если победит Слава, или "Ollie wins.", если победит Оля.
Пусть игра уже закончена и получено число p in [n; +oo). Рассмотрим последние ходы: очевидно, что такое число p можно получить из числа p_0, находящегося в диапазоне [ceil(n/9); n-1]. Другой игрок, в свою очередь при любом раскладе получит число p_0 из числа p_1 из диапазона [ceil(ceil(n/9) / 2), ceil(n/9) - 1)]; То есть задача "победить в игре" свелась к задаче "получить число p1 in [ceil(ceil(n/9) / 2); ceil(n/9) - 1)]". Очевидно, что данная задача эквивалентна исходной, просто диапазон будет другим: p_1 получается из p_2 in [ceil(n_0 / 9); n_0 - 1]; p_2 получается из p_3 in [ceil(ceil(n_0 / 9) / 2); ceil(n_0 / 9) - 1)], где n_0 = ceil(ceil(n/9) / 2). В итоге имеем задачу "получить p_3" и т. д.
то есть ceil(n'/9) - нижняя граница выигрышного диапазона. ceil(ceil(n'/9) / 2) - левая граница проигрышного диапазона. n' - это n, n_0... Нужно определить, левой границей какого диапазона является 1. Если выигрышного, то побеждает Stan, а иначе - Ollie.
Ну и кодится это довольно просто:
from math import ceil
n, c, d = int(input()), 0, [9, 2]
while n > 1:
n = ceil(n / d[c % 2])
c += 1
print("Stan wins." if c % 2 == 1 else "Ollie wins.")
Если кратко, то нужно по очереди делить N на 2 и на 9. В зависимости от того, на каком делении мы получим 1, можно будет сказать, кто выигрывает.
Суть в том, что мы каждое значение P можем пометить как выигрышное или проигрышное и ввести рекуррентные правила: 1) если P>=N, то оно проигрышное, 2) если есть ход в проигрышное значение, то оно выигрышное и 3) если все ходы в выигрышные значения, то текущее значение проигрышное.
По этим правилам нужно идти обратно от N до 1 и смотреть, каким получится 1.
Очевидно, что выигрышные и проигрышные значения будут группироваться в довольно крупные отрезки. Например, есть отрезок проигрышных с N до бесконечности и отрезок выигрышных с N/9 до N.
Можно показать, что длина отрезка зависит только от длины его соседнего отрезка справа (т. е. с большими числами) с обратной "выигрышностью". Это основано на двух фактах, которые можно доказать: 1) если мы рассматриваем участок чисел, начинающийся в 1, и правая половина этого отрезка проигрышная, то отрезок с 1/18 до 1/2 выигрышен и 2) если 8/9 справа такого участка выигрышна, то отрезок с 1/18 до 1/9 проигрышен.
Советую сесть и порисовать отрезки, чтобы это переварить, а потом сравнить с выхлопом текущего решения и определиться с мелочами, т. е. понять, как это закодить. Округления там всякие, например.
В конце концов, неэффективное решение на 62 процента у тебя есть, значит, сравнивать на правильность есть с чем.
