1 Тема від taras161514 Востаннє редагувалося leofun01 (21.10.2018 01:01:42)

  • taras161514
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.10.2018
  • Повідомлень: 1
    • Репутація: 1

Тема: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

Попередня назва теми: Задача Гра, допоможіть розвязати

Максимко та Дмитрик грають у цікаву гру. На столі лежать дві купки з А та В горішків. Максим починає завжди першим і хлопці роблять ходи по черзі. За один хід можна зробити одну з таких дій:

• З’їсти один горішок з будь-якої купки.
• З’їсти по одному горішку з обох купок.
• Перекласти один горішок з однієї купки на іншу.

Виграє гру той гравець, що з’їдає останній горішок. Максимко та Дмитрик нескінченно розумні, а тому грають оптимально. Напишіть програму, яка визначає результат гри: виводить 1 – якщо переможе Максим, 2 – якщо переможе Дмитро та 0 – якщо гра ніколи не закінчиться.

Формат вхідних даних
З вхідного потоку уводиться два цілих числа A і B (1 <= A,B <= 2000000000), що розділені пробілами.

Формат вихідних даних
У вихідний потік необхідно вивести число 1, якщо гра завершиться перемогою Максима; число 2, якщо гра завершиться перемогою Дмитрика; число 0, якщо гра ніколи не завершиться.

Подякували: leofun011

2 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

то вам треба симулювати гру тих хлопаків, і при кожному кроці робити оптимальний хід?

3 Відповідь від cheappi386

  • cheappi386
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 19.08.2015
  • Повідомлень: 1 142
    • Репутація: 381

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

FakiNyan написав:

то вам треба симулювати гру тих хлопаків, і при кожному кроці робити оптимальний хід?

Це й мав на у вазі викладач, але бач пан хоче розв'язок задачі на халяву...

4 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

так тут тре спочатку про сам алгоритм подумати, а лише потім писати код, але в будь-якому разі юзера можна сміливо банити, а тему переносити в кошик

5 Відповідь від leofun01 Востаннє редагувалося leofun01 (21.10.2018 01:03:29)

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

taras161514 написав:

Максимко та Дмитрик грають у цікаву гру...

• З’їсти один горішок з будь-якої купки.
• З’їсти по одному горішку з обох купок.
• Перекласти один горішок з однієї купки на іншу.

В таких випадках потрібно давати посилання на джерело.

cheappi386 написав:
FakiNyan написав:

то вам треба симулювати гру ...

Це й мав на у вазі викладач

Нажаль, більшість викладачів формують задачі не так чітко.

taras161514 написав:

допоможіть розвязати

Побудуємо таблицю виграшів на основі чисел A і B, де (A < B).
Почнемо з того, що дано :

    B   0   1   2
A   +---------------
0   |   2   1   2
1   |       1

Далі будемо додавати по одній діагоналі до таблиці починаючи з першого рядка.
Додавання чисел буде проходити за правилом:
Якщо в сусідніх клітинках стоїть "1" (через і) як показано тут

    B  m-1  m  m+1
A   +--------------
n-1 |   1   1   1
n   |   1   x
n+1 |   1

, то будемо ставити "2" (в клітинку, де "(A == n) && (B == m)").
Але якщо хоча б в одній із тих клітинок (там, де "1") стоїть "2", то ставимо "1".
Погнали

    B   0   1   2   3
A   +-------------------
0   |   2   1   2   1
1   |       1   1
#===========================
    B   0   1   2   3   4
A   +-----------------------
0   |   2   1   2   1   2
1   |       1   1   1
2   |           2
#===============================
    B   0   1   2   3   4   5
A   +---------------------------
0   |   2   1   2   1   2   1
1   |       1   1   1   1
2   |           2   1
#===================================
    B   0   1   2   3   4   5   6
A   +-------------------------------
0   |   2   1   2   1   2   1   2
1   |       1   1   1   1   1
2   |           2   1   2
3   |               1

і так далі ...
Потім знімаємо обмеження (A < B), тобто робимо симетричне доповнення таблиці :

    B   0   1   2   3   4   5   6
A   +-------------------------------
0   |   2   1   2   1   2   1   2
1   |   1   1   1   1   1   1   1
2   |   2   1   2   1   2   1   2
3   |   1   1   1   1   1   1   1
4   |   2   1   2   1   2   1   2
5   |   1   1   1   1   1   1   1
6   |   2   1   2   1   2   1   2

Маємо регулярну схему, з якої можна вивести алгоритм і формулу, яка буде повертати номер гравця, який виграє в цій грі :
2 - ((A | B) & 1)
зроблено на основі стандартного двійкового преставлення цілих чисел.

upd: Поміняв назву теми. Не годиться писати в заголовку "допоможіть".

leofun01 вебсайт

6 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 278
    • Репутація: 2720

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

В них там є помилки в тестах (станом на 2018-10-21).
Для цієї гри не існує таких скінченних A і B, щоб результат був 0 (нескінченною грою).
Я залишив там коментар, сподіваюсь вони помітять.

leofun01 вебсайт

7 Відповідь від FakiNyan

  • FakiNyan
  • FakiNyan
  • Робітниця.
  • Поза форумом
  • Дата реєстрації: 27.06.2013
  • Повідомлень: 14 097
    • Репутація: 5660

Re: Максимко та Дмитрик грають у цікаву гру. Дві купки горішків.

▼Прихований текст
leofun01 написав:
taras161514 написав:

Максимко та Дмитрик грають у цікаву гру...

• З’їсти один горішок з будь-якої купки.
• З’їсти по одному горішку з обох купок.
• Перекласти один горішок з однієї купки на іншу.

В таких випадках потрібно давати посилання на джерело.

cheappi386 написав:
FakiNyan написав:

то вам треба симулювати гру ...

Це й мав на у вазі викладач

Нажаль, більшість викладачів формують задачі не так чітко.

taras161514 написав:

допоможіть розвязати

Побудуємо таблицю виграшів на основі чисел A і B, де (A < B).
Почнемо з того, що дано :

    B   0   1   2
A   +---------------
0   |   2   1   2
1   |       1

Далі будемо додавати по одній діагоналі до таблиці починаючи з першого рядка.
Додавання чисел буде проходити за правилом:
Якщо в сусідніх клітинках стоїть "1" (через і) як показано тут

    B  m-1  m  m+1
A   +--------------
n-1 |   1   1   1
n   |   1   x
n+1 |   1

, то будемо ставити "2" (в клітинку, де "(A == n) && (B == m)").
Але якщо хоча б в одній із тих клітинок (там, де "1") стоїть "2", то ставимо "1".
Погнали

    B   0   1   2   3
A   +-------------------
0   |   2   1   2   1
1   |       1   1
#===========================
    B   0   1   2   3   4
A   +-----------------------
0   |   2   1   2   1   2
1   |       1   1   1
2   |           2
#===============================
    B   0   1   2   3   4   5
A   +---------------------------
0   |   2   1   2   1   2   1
1   |       1   1   1   1
2   |           2   1
#===================================
    B   0   1   2   3   4   5   6
A   +-------------------------------
0   |   2   1   2   1   2   1   2
1   |       1   1   1   1   1
2   |           2   1   2
3   |               1

і так далі ...
Потім знімаємо обмеження (A < B), тобто робимо симетричне доповнення таблиці :

    B   0   1   2   3   4   5   6
A   +-------------------------------
0   |   2   1   2   1   2   1   2
1   |   1   1   1   1   1   1   1
2   |   2   1   2   1   2   1   2
3   |   1   1   1   1   1   1   1
4   |   2   1   2   1   2   1   2
5   |   1   1   1   1   1   1   1
6   |   2   1   2   1   2   1   2

Маємо регулярну схему, з якої можна вивести алгоритм і формулу, яка буде повертати номер гравця, який виграє в цій грі :
2 - ((A | B) & 1)
зроблено на основі стандартного двійкового преставлення цілих чисел.

upd: Поміняв назву теми. Не годиться писати в заголовку "допоможіть".

нічого не зрозумів  *SCRATCH*