Искрине поздравляю с выходом в финал !!! Очень-очень достойно!
Почти половина финалистов - из России )))
Максим, удачи в финале !!!
P.S. А я продолжу работу над ошибками и анализ задач
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от Anton
Страницы 1
Искрине поздравляю с выходом в финал !!! Очень-очень достойно!
Почти половина финалистов - из России )))
Максим, удачи в финале !!!
P.S. А я продолжу работу над ошибками и анализ задач
Спасибо за разъяснения! Почти всё встало на свои места, все рассуждения очень логичные.
Маленький вопрос касательно финального сдвига на res / (k-1), его логический смысл мне ясен, не понимаю аналитическую часть - почему k-ых бойцов до позиции res ровно res / (k-1) ?
Я пробовал рассматривать разные примеры, допустим n=6, k=3. Выписываю их индексы (в 0-индексации):
0 1 2 3 4 5
^ ^
k-ые бойцы - 2 и 5. Теоретически (чисто теоретически) подзадача с n=4, k=3 возвращает нам ответ в диапозоне [0;4]; диапозон, который соответствует случаю 2б), - [0;4]. Допустим, если подзадача вернула 4 то res / (k-1) = 2. То есть до бойца с позиции 4 стоит 2 k-ых бойца, но это ведь не так ...
Подскажите, пожалуйста, какие рассуждения я провожу не верно ?
Кстати, попробовал обойтись только вариантом 2б) на последнем шаге (без строчек 6 и 7) - увы, не выходит. Это можно увидеть, к примеру, при n=3, k=2.
Знаю, задача и ее решение уже обмусолены с разных сторон.
Меня интересует реализация решения за k(log(n)). Хочу полностью понять логику.
Разбираю функцию построчно:
1. if (n == 1) return 0; // это понятно
2. if (k == 1) return n-1; // это понятно
3. if (k > n) return (joseph (n-1, k) + k) % n; // это понятно
*4. int cnt = n / k; // сколько k-ых бойцов в кругу
*5. int res = joseph (n - cnt, k); // считаем для ситуации после экзекуции всех k-ых бойцов
*6. res -= n % k; // - ?
*7. if (res < 0) res += n; // - ?
*8. else res += res / (k - 1); // - ???
Хотелось бы полуить комментарии по строкам 4-8.
В теоретических материалах в сети не удалось найти подобных формулировок.
Zayakin_Andrey, привет.
Не совсем понимаю логику переходов между состояними ...
Если dp[ X ] - проигрышная (или не оцененная), то основываясь на чем, мы делаем вывод, что dp[ X + m[ k ] ] - выигрышная ?
И если dp[ X ] - выигрышная, то какова тут цепочка рассуждений ?
Хочу понять этот принцип, он много где встречается. Объяни, пожалуйста
Страницы 1
MAXimal :: φορυμ » Сообщения от Anton