Игра в монеты С++

@arteman152 · Регистрация: 28.02.2014

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

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

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

Входные данные

: число стопок N (1 <= N <= 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке — не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 <= K <= 80). Все числа в строке разделены пробелом.

Выходные данные

1. Организовать игру

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

Нашел в интернете математическое решение:
Введем обозначения: s[r] − суммарное количество монет в стопках с r-той по n-ю; g[r, m] − максимальное количество монет, которое может получить игрок, если сейчас его ход, при условии что остались стопки с r-той по n-ю, и он может взять не более m стопок. Элементы массива s[1..n] будут использоваться для вычисления элементов массива g[n, k], поэтому его нужно вычислить и сохранить сразу после ввода данных.

Далее вычисляем элементы массива g. Если игрок может взять все оставшиеся стопки, то он должен сделать это, иначе другой игрок возьмет не менее одной стопки из оставшихся стопок, и выигрыш игрока , чей сейчас ход, не будет максимальным. Следовательно, все числа g[r, m], где m ≥ n − r + 1, определены, в том числе все элементы g[n, m]. А именно, g[r, m]=s[r].

Будем находить элементы g[r, m] в порядке убывания r, при условии m < n − r + 1 . В этой ситуации игрок может взять от одной до m стопок. Пусть он взял i стопок. Тогда другой игрок окажется в ситуации (r + i, i) − его ход, разыгрываются стопки с (r + i) − той по n − ю, и можно взять не более i стопок. Он может взять максимальное количество монет, равное g[r + i, i]. Так как в стопках с r-той по n-ю было s[r] монет, то первый игрок , взяв i стопок, получит s[r] − g[r+i, i] монет.
Поэтому максимальный выигрыш первого игрока определяется по формуле:
Ответом задачи будет число g[1, k] − столько монет может получить первый игрок, если разыгрываются стопки с 1-й по n-ю и можно взять не более k стопок.

Черновик кода

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
#include <iostream>
#include<fstream>
 
using namespace std;
 
const int n = 180;
 
int main()
{
    int i;
    int A[n];
 
    for (i = 0; i < n; i++)
    {
        A[i] = rand() % 20000;
    }
    cout << endl;
 
    for (i = 0; i < n; i++)
    {
        {
            cout << A[i] << "\t";
        }
    }
    cout << endl;
    system("pause");
}

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

@nmcf · 24.05.2018, 09:39

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

чтобы они в сумме давали 20000 монет

Зачем? В задании же нет ограничения на общее количество.

@arteman152 · 25.05.2018, 08:22 **[ТС]**

Ну я просто так понял задание, что нужно разложить 20000 монет в 180 стопок

Добавлено через 22 часа 40 минут
help please guys!

@_Ivana · 26.05.2018, 15:03

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 180, K = 80;
int a[N], n, d[K+1][N+1];
 
int s(int i) { return i >= n ? 0 : a[i] + s(i+1); }
 
int f(int, int);
 
int l(int j, int r, int i) { return j <= 0 ? r : l(j-1, max(r, s(i) - f(j, i+j)), i); }
 
int f(int k, int i) { if (!d[k][i]) d[k][i] = l(min(k, n-i), 0, i); return d[k][i]; }
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int k; cin >> k;
    cout << f(k, 0);
}

Code
1
2
3
4
5
6
7
8
9
10
11
Тест    Результат  Время  Память
1   Accepted    0,03    340 Кб
2   Accepted    0,03    340 Кб
3   Accepted    0,03    340 Кб
4   Accepted    0,03    340 Кб
5   Accepted    0,03    340 Кб
6   Accepted    0,03    340 Кб
7   Accepted    0,03    340 Кб
8   Accepted    0,03    340 Кб
9   Accepted    0,03    340 Кб
10  Accepted    0,062   340 Кб

PS Хорошая задачка

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@arteman152 0 / 0 / 0 Регистрация: 28.02.2014 Сообщений: 25
	25.05.2018, 08:22 [ТС]
	Ну я просто так понял задание, что нужно разложить 20000 монет в 180 стопок Добавлено через 22 часа 40 минут help please guys! 0

Игра в монеты С++

Решение