Задача с пешкой (acmp 787)

@constantin_01 · Регистрация: 30.04.2019

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

Здравствуйте!

Условие задачи в приложении.

Мне не совсем ясно, что предполагается под "гарантированный выигрыш первого игрока". Ясно, что каждый ход первый игрок будет выбирать максимум из диагональных элементов, а второй - минимум. Однако как этот выбор будет сделан не понятно.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int k = 1;
 
    bool stop = false;
    while (!stop)
    {
        if ( i == j ) 
        { 
            stop = true;
            break;
        }
        else
        {
            if ( (k % 2) == 0 )
            {
                if ( desk[j][j] < desk[i][i] )
                {
                    i = i - 1;
                    cout << "Player 2: up" << endl;
                }
                else
                {
                    j = j + 1;
                    cout << "Player 2: right" << endl;
                }
            }
            if ( (k % 2) != 0 )
            {
                if ( desk[i][i] > desk[j][j] )
                {
                    j = j + 1;
                    cout << "Player 1: right" << endl;
                }
                else
                {
                    i = i - 1;
                    cout << "Player 1: up" << endl;
                }
 
            }
            k = k + 1;
        }
    }

@Shamil1 · 01.07.2019, 12:08

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

Мне не совсем ясно, что предполагается под "гарантированный выигрыш первого игрока".

Минимум, который он (при оптимальной игре) гарантированно выиграет, даже если оппонент будет играть оптимально.

Добавлено через 3 минуты

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

Однако как этот выбор будет сделан не понятно.

Поставить "напротив" (по диагонали из левого нижнего в правый верхний) желаемого числа.

@Ethereal · 03.07.2019, 07:03

Мне не совсем ясно, что предполагается под "гарантированный выигрыш первого игрока".

Во первых в этой игре первый игрок всегда выигрывает, а во вторых для него есть стратегия гарантированно выиграть не меньше 5-и. Если не существует стратегии гарантированно выиграть больше 5-и, тогда гарантированный выигрыш первого игрока 5.

Добавлено через 4 минуты

Однако как этот выбор будет сделан не понятно.

Да какой предложишь.
Я предлагаю такой выбор для первого игрока :
1.) Первый ход направо.
2.) На каждый ход второго игрока возвращать пешку на диагональ ведущую к пятерке. Итого выигрываем минимум 5.
Но то, что лучше этой стратегии не существует надо еще доказать.

@0x10 · 03.07.2019, 15:05

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

Во первых в этой игре первый игрок всегда выигрывает

Игрок 1 всегда доходит до диагонали, но у игрока 2 есть возможность уменьшить выигрыш.

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

для него есть стратегия гарантированно выиграть не меньше 5-и

Для частного случая. По условию задачи числа на диагонали определяются входными данными.

constantin_01, задача сильно проще, чем кажется. В решении нет необходимости вычислять весь путь.

@Ethereal · 03.07.2019, 17:02

Игрок 1 всегда доходит до диагонали, но у игрока 2 есть возможность уменьшить выигрыш.

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

Для частного случая.

А в общем случае задача решается так :

N1=MAX(N1,N2) N2=MAX(N2,N3) N3=MAX(N3,N4) N4=MAX(N4,N5) N5=MAX(N5,N6) N6=MAX(N6,N7) N7=MAX(N7,N8)
N1=MIN(N1,N2) N2=MIN(N2,N3) N3=MIN(N3,N4) N4=MIN(N4,N5) N5=MIN(N5,N6) N6=MIN(N6,N7)
N1=MAX(N1,N2) N2=MAX(N2,N3) N3=MAX(N3,N4) N4=MAX(N4,N5) N5=MAX(N5,N6)
N1=MIN(N1,N2) N2=MIN(N2,N3) N3=MIN(N3,N4) N4=MIN(N4,N5)
N1=MAX(N1,N2) N2=MAX(N2,N3) N3=MAX(N3,N4)
N1=MIN(N1,N2) N2=MIN(N2,N3)
N1=MAX(N1,N2)
Результат = N1

И в данном частном случае ответ выходит 5. И выигрышная стратегия расписывается в двух пунктах.

Добавлено через 8 минут
Вот так сосчитал

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE ДИАГОНАЛЬ 3 C, 1 C, 4 C, 1 C, 5 C, 9 C, 2 C, 6 C,
 
: ГАРАНТИРОВАННЫЙ-ВЫИГРЫШ
  ( -- n )
  1 7 DO
    I 0 DO
      ДИАГОНАЛЬ I +
      DUP C@ OVER 1+ C@ J 1 AND IF MAX ELSE MIN THEN
      SWAP C!
    LOOP
  -1 +LOOP
  ДИАГОНАЛЬ C@
;
 
ГАРАНТИРОВАННЫЙ-ВЫИГРЫШ . BYE

на богом забытом языке.

Добавлено через 11 минут
Причем кажется алгоритм можно еще упростить до одного прохода по массиву чисел на диагонали.

Добавлено через 6 минут
Хотя не факт.

@Shamil1 · 03.07.2019, 17:46

Для чётного N:
Изначально пешка стоит на диагонали, проходящей между двумя числами. Первый игрок может выбрать, на диагональ с каким из этих двух чисел поставить пешку. В дальнейшем он может каждым ходом возвращать пешку на эту диагональ. Число на диагонали - гарантированный выигрыш первого игрока. Оптимальная стратегия - сравнить два числа и поставить пешку на диагональ с большим из них.
Одна из оптимальных стратегий для второго игрока (при условии, что первый играет оптимально) - каждый раз возвращать пешку на главную диагональ. Таким образом, первый игрок получает тот же самый выбор, а значит не сможет улучшить свой гарантированный выигрыш.

В данном примере выбор между 1 и 5. Первый игрок выбирает 5 (ходит вправо). Второй игрок возвращает выбор между 1 и 5 (ходит вверх). Если второй игрок сыграет неправильно (вправо), то у первого игрока появится выбор между 5 и 9, он выберет 9 и улучшит свой гарантированный выигрыш.
Если бы числа были х1, х2, х3, 3, 5, 1, х7, х8, то второй игрок (в надежде на ошибку первого игрока) мог бы пойти вправо, заменяя выбор между 3 и 5 на выбор между 5 и 1. Но если первый игрок ходит правильно, то смысла в этом нет - всё равно он выберет 5.

Добавлено через 4 минуты
Для нечётного N примерно то же самое, только придётся рассмотреть не два, а три числа. Гарантированным выигрышем будет max( min(x1,x2), min(x2,x3) ). По сути, первый игрок выбирает, выбор из каких двух соседних чисел предоставить второму игроку.

@vantfiles · 07.07.2019, 13:14

Не по теме:

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

на богом забытом языке.

Forth как Forth, зачем его забывать. я, к примеру, вполне успешно использую его в качестве скриптового языка в проектах на с++.

Новые блоги и статьи Все статьи Все блоги /
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,876
	03.07.2019, 17:46
	Для чётного N: Изначально пешка стоит на диагонали, проходящей между двумя числами. Первый игрок может выбрать, на диагональ с каким из этих двух чисел поставить пешку. В дальнейшем он может каждым ходом возвращать пешку на эту диагональ. Число на диагонали - гарантированный выигрыш первого игрока. Оптимальная стратегия - сравнить два числа и поставить пешку на диагональ с большим из них. Одна из оптимальных стратегий для второго игрока (при условии, что первый играет оптимально) - каждый раз возвращать пешку на главную диагональ. Таким образом, первый игрок получает тот же самый выбор, а значит не сможет улучшить свой гарантированный выигрыш. В данном примере выбор между 1 и 5. Первый игрок выбирает 5 (ходит вправо). Второй игрок возвращает выбор между 1 и 5 (ходит вверх). Если второй игрок сыграет неправильно (вправо), то у первого игрока появится выбор между 5 и 9, он выберет 9 и улучшит свой гарантированный выигрыш. Если бы числа были х1, х2, х3, 3, 5, 1, х7, х8, то второй игрок (в надежде на ошибку первого игрока) мог бы пойти вправо, заменяя выбор между 3 и 5 на выбор между 5 и 1. Но если первый игрок ходит правильно, то смысла в этом нет - всё равно он выберет 5. Добавлено через 4 минуты Для нечётного N примерно то же самое, только придётся рассмотреть не два, а три числа. Гарантированным выигрышем будет max( min(x1,x2), min(x2,x3) ). По сути, первый игрок выбирает, выбор из каких двух соседних чисел предоставить второму игроку. 0

Опции темы