Задача с пешкой (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, зачем его забывать. я, к примеру, вполне успешно использую его в качестве скриптового языка в проектах на с++.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Shamil1 Модератор 3132 / 2279 / 469 Регистрация: 26.03.2015 Сообщений: 8,870
	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