Теория игр. Шоколадка

@aKrass · Регистрация: 19.09.2023

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

Здравствуйте! Никак не могу решить задачу. Моё решение проходит 70% тестов (9/30) тестов. Пытался найти закономерность через четность/нечестность площади шоколадки, ее размерам. Само условие (открытых тестов нету):
Двое играют в такую игру: перед ними лежит шоколадка размера NxM.
За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".
Однако, нельзя разламывать куски размером не больше, чем 1×k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 1×1, 1×2, ……, 1×k, а остальные куски разламывать можно.
Проигрывает тот, кто не может сделать ход.
Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.
Входные данные
Вводятся целые числа 0 < N, M, K <= 100.
Выходные данные
Вывести 1 или 2 - номер игрока, который выиграет при правильной игре.

Моё решение:

Python
1
2
3
4
5
6
7
n, m, k = map(int, input().split())
if n * m <= k:
  print(2)
elif (n < k and m > k) or (n > k and m < k):
  print(1)
else:
  print(1 if n * m % k == 0 else 2)

Помогите найти ошибку, пожалуйста)

@aKrass · 24.02.2024, 18:13 **[ТС]**

Нашел некоторые открытые тесты:
Ввод: 2 2 1
Вывод: 1

Ввод: 1 1 1
Вывод: 2

@aKrass · 25.02.2024, 21:22 **[ТС]**

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

Нашел некоторые открытые тесты:

Еще:

Ввод: 1 2 2
Вывод: 2

Ввод: 3 2 3
Вывод: 1

@Aael · 01.03.2024, 10:00

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

Однако, нельзя разламывать куски размером не больше, чем 1×k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части).

дурацкая формулировка..

aKrass, Теория Шпрага-Гранди. Grundy's game

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from functools import cache
 
@cache
def score(n, m, k):
    if n == 1 and m <= k or m == 1 and n <= k:
        return 0
    
    next_scores = set()
    for i in range(1, n):
        g = score(i, m, k) ^ score(n-i, m, k) 
        next_scores.add(g)
 
    for i in range(1, m):
        g = score(n, i, k) ^ score(n, m-i, k) 
        next_scores.add(g)
 
    for i in range(len(next_scores) + 1):
        if i not in next_scores: 
            return i
 
n, m, k = map(int, input().split())
print(1 if score(n, m, k) > 0 else 2)

@aKrass · 01.03.2024, 18:51 **[ТС]**

Aael, спасибо вам огромное! За теорию отдельная благодарность)

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

@aKrass 1 / 1 / 0 Регистрация: 19.09.2023 Сообщений: 33
	24.02.2024, 18:13 [ТС]
	Нашел некоторые открытые тесты: Ввод: 2 2 1 Вывод: 1 Ввод: 1 1 1 Вывод: 2 0

@aKrass 1 / 1 / 0 Регистрация: 19.09.2023 Сообщений: 33
	01.03.2024, 18:51 [ТС]
	Aael, спасибо вам огромное! За теорию отдельная благодарность) 0

Теория игр. Шоколадка

Решение