Игра в камушки

@MrMelya · Регистрация: 29.09.2017

Студворк — интернет-сервис помощи студентам

Двое играют в игру “Камушки”. В начале этой игры перед участниками лежит кучка из n камней. Игроки ходят по очереди. На своем ходу игрок может взять из кучки 1, 2 или k камней. Проигрывает тот, кто не может сделать ход.

По заданным числам n и k определите, кто из игроков может гарантировать себе победу, независимо от того, как будет действовать другой игрок.

Формат ввода

В первой строке дано целое число n, 1 ≤ n ≤ 10⁴.

Во второй строке дано целое число k, 3 ≤ k ≤ 10⁴.

Формат вывода

Выведите число “1” (без кавычек), если первый игрок может гарантировать себе победу, независимо от действий второго игрока. В противном случае выведите число “2” (без кавычек).

Пример 1

ввод	вывод
3 3	1

Пример 2

ввод	вывод
4 3	2

@Puporev · 09.09.2020, 12:14

Сообщение от MrMelya

1 ≤ n ≤ 104.

Наверняка 10⁴

@MrMelya · 09.09.2020, 12:23 **[ТС]**

Да, не уследил

@Cyborg Drone · 09.09.2020, 16:40

Исправил.

@mr-Crocodile · 10.09.2020, 10:01

MrMelya, в подобных задачах обычно самое сложное это найти выигрышную стратегию. Очевидно, что в данном случае от N и K зависит, какой игрок сможет победить.
Ты уже определил эту стратегию? Тогда запрограммировать её - не сложно.
если этой стратегии нет, то нужно её искать.

@Cyborg Drone · 11.09.2020, 09:59

Не знаю. как ТС, но мне пока не удалось найти выигрышную стратегию. Начинаю подозревать. что ограничение чисел до 10⁴ не напрасное.

@mr-Crocodile · 11.09.2020, 10:19

Сообщение от Cyborg Drone

Начинаю подозревать. что ограничение чисел до 10⁴ не напрасное.

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

@ProMix0 · 11.09.2020, 15:31

Сообщение от mr-Crocodile

можно перебрать все варианты

Да не, такие задачки в школах задают (конкретно эту) или на олимпиадах. Правда решение я уже не помню, если хоть знал его

@eaa · 11.09.2020, 15:38

зачем перебирать?! ответ очевидно зависит от чётности k.

Добавлено через 1 минуту
ну и от чётности n

@mr-Crocodile · 11.09.2020, 15:41

Сообщение от eaa

ответ очевидно зависит от чётности k.

ну и от чётности n

ну, мне, например, не очевидно

можно пример/формулу/пояснение?

@ProMix0 · 11.09.2020, 15:42

Сообщение от eaa

от чётности

Скорее от кратности

@eaa · 11.09.2020, 16:18

ДП чтоли?! хм...

@Cyborg Drone · 11.09.2020, 16:53

ProMix0, не особенно-то и зависит. Если при k=3 выигрышная стратегия "оставлять кратное 4 количество" работает, то даже при k=4 или k=5 "оставлять кратное k+1 количество" не работает. Не проходят и другие кратности: при k=12 не получится использовать ни "оставлять кратное 12 количество", ни "оставлять кратное 4 количество". Кстати, n определяет только лишь кому из игроков достанется неведомая выигрышная стратегия. И вряд ли это определяет чётность n, скорее, его величина. Выигрышная стратегия может зависеть от комбинации чётностей n и k, но это далеко не обязательно. Хотелось бы, чтобы так и было, однако, это только ничем не подтверждённая хотелка.

Сообщение от eaa

ответ очевидно зависит от чётности

eaa, Вы уверены? Сказали "а", так скажите и "б". Напишите для нас, пожалуйста, Ваше решение. Меня прямо-таки съедает любопытство. И ещё непонимание того, что именно Вы имеете ввиду. Как бы я не предполагал использовать чётность n и k, а также их комбинацию чётностей, у меня самого на каждое моё предположение нашёлся контрпример. Скажите, которую очевидность я мог не заметить?

Добавлено через 2 минуты
Ой. Надо было обновить страницу. eaa, жаль, что Вам не удалось найти выигрышную стратегию.

@eaa · 11.09.2020, 16:56

Pascal
1
2
3
4
5
6
7
8
9
10
11
begin
  var (n, k) := ReadInteger2;
  var d := ArrFill(n + 1, 2);
  for var i := 1 to n do
  begin
    if d[i - 1] = 2 then d[i] := 1;
    if (i >= 2) and (d[i - 2] = 2) then d[i] := 1;
    if (i >= k) and (d[i - k] = 2) then d[i] := 1
  end;
  d.Last.Print
end.

@mr-Crocodile · 11.09.2020, 17:14

eaa, красота!

p.s. как я понимаю - это ДП?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@MrMelya 0 / 0 / 0 Регистрация: 29.09.2017 Сообщений: 6
	09.09.2020, 12:23 [ТС]
	Да, не уследил 0

@Cyborg Drone Модератор 10437 / 5726 / 3405 Регистрация: 17.08.2012 Сообщений: 17,433
	09.09.2020, 16:40
	Исправил. 1

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,380
	10.09.2020, 10:01
	MrMelya, в подобных задачах обычно самое сложное это найти выигрышную стратегию. Очевидно, что в данном случае от N и K зависит, какой игрок сможет победить. Ты уже определил эту стратегию? Тогда запрограммировать её - не сложно. если этой стратегии нет, то нужно её искать. 1

@Cyborg Drone Модератор 10437 / 5726 / 3405 Регистрация: 17.08.2012 Сообщений: 17,433
	11.09.2020, 09:59
	Не знаю. как ТС, но мне пока не удалось найти выигрышную стратегию. Начинаю подозревать. что ограничение чисел до 10⁴ не напрасное. 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	11.09.2020, 15:38
	зачем перебирать?! ответ очевидно зависит от чётности k. Добавлено через 1 минуту ну и от чётности n 2

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	11.09.2020, 16:18
	ДП чтоли?! хм... 0

@mr-Crocodile 3053 / 1672 / 657 Регистрация: 19.03.2019 Сообщений: 5,380
	11.09.2020, 17:14
	eaa, красота! p.s. как я понимаю - это ДП? 0

Игра в камушки

Решение