Найти счёт при оптимальной стратегии двух игроков

@dzrkot · Регистрация: 11.09.2013

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

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

Игроки совершают ходы по очереди. На каждом ходу игрок забирает число, написанное в его текущей ячейке, затем ставит туда ноль и переходит в смежную слева или справа ячейку (разумеется, игрок не может выходить за пределы массива). Два игрока могут в некоторый момент времени находиться в одной ячейке. Счёт игрока — это сумма всех набранных во время игры чисел. Игра заканчивается, когда во всех ячейках массива записаны нули.
А теперь вычислите, какое максимальное количество очков могут набрать первый и второй игроки (первый игрок, разумеется, ходит первым), если они играют оптимально, то есть стремятся максимизировать свой счёт, а если существует несколько вариантов сделать это, то стараются минимизировать счёт противника.

Исходные данные:
В первой строке записано целое число n — размер массива (10 ≤ n ≤ 105). Во второй строке записаны n целых чисел — исходный массив. Все элементы массива неотрицательны и не превосходят 10 000. В третьей строке записаны два целых числа — стартовые позициии первого и второго игроков соответственно. Индексация ячеек массива начинается с единицы.

Результат:
Выведите два числа — счёт первого и второго игроков при оптимальной игре обоих.
Пример:
исходные данные :
10
1 2 3 4 5 6 7 8 9 0
4 8
результат:
21 24

@Kukurudza · 09.07.2014, 15:04

может я ошибаюсь или что-то не так насчитал, но у меня получилось так:
4 8
5 9
6 0
7 1
0 2
0 3
22 и 23 соответственно
а пардон, я зациклил массив

видимо так нельзя

@dzrkot · 09.07.2014, 15:20 **[ТС]**

хм... по идее главное сразу идти в сторону соперника, т.к. потом в любом случае мы идём в обратную сторону от него и он уже не успеет собрать то, что будет подбирать др игрок, т.е. игроку 1 (условно он слева) надо дойти до player2-1 позиции 2ого игрока,п осле чего бежать в обратку, соответственно 2ому аналогично...

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

@soon · 09.07.2014, 15:33

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

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

Нет, тут вообще вопрос лишь в том, кто находится справа, а кто слева.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <numeric>
 
int main()
{
    std::size_t n;
    std::cin >> n;
 
    std::vector<std::size_t> v(n);
    for(auto& elem: v)
    {
        std::cin >> elem;
    }
 
    std::size_t f, s;
    std::cin >> f >> s;
 
    --f;
    --s;
 
    std::size_t sum_f = 0;
    std::size_t sum_s = 0;
 
    if(f < s)
    {
        sum_f = std::accumulate(v.begin(), v.begin() + f + 1, 0);
        sum_s = std::accumulate(v.begin() + s, v.end(), 0);
 
        --s;
 
        while(f < s)
        {
            sum_f += v.at(++f);
            if(f != s)
            {
                sum_s += v.at(s--);
            }
        }
    }
    else if(f == s)
    {
        // sum_f = std::accumulate(v.begin(), v.begin() + f + 1, 0);
        // sum_s = std::accumulate(v.begin() + s + 1, v.end(), 0);
        auto sum_l = std::accumulate(v.begin(), v.begin() + f, 0);
        auto sum_r = std::accumulate(v.begin() + f + 1, v.end(), 0);
 
        sum_f = std::max(sum_l, sum_r) + v.at(f);
        sum_s = std::min(sum_l, sum_r);
    }
    else
    {
        sum_f = std::accumulate(v.begin() + f, v.end(), 0);
        sum_s = std::accumulate(v.begin(), v.begin() + s + 1, 0);
 
        --f;
 
        while(f > s)
        {
            sum_f += v.at(f--);
            if(f != s)
            {
                sum_s += v.at(++s);
            }
        }
    }
 
    std::cout << sum_f << ' ' << sum_s << std::endl;
 
    return 0;
}

@dzrkot · 09.07.2014, 16:23 **[ТС]**

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

Нет, тут вообще вопрос лишь в том, кто находится справа, а кто слева.

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

Добавлено через 9 минут
вроде тоже сделал

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
43
44
45
46
47
48
49
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <windows.h>
using namespace std;
 
int main()
{
srand(time(0));
int n;
int pl1,pl2;
n=10+rand()%15;
int *a=new int[n];
pl1=1+rand()%n;
pl2=1+rand()%n;
if(pl1>pl2)
    swap(pl1,pl2);
 
  for (;pl1==pl2;)
    pl2=rand()%n;
 
for(int i=1;i<n;i++)
  {
  cout<<setw(3)<<(a[i]=rand()%10);
  }
cout<<endl<<"pos player 1 = "<<pl1<<endl<<"pos player 2 = "<<pl2;
  int sum1=0;
  int sum2=0;
 
  for (int i=0;pl1<pl2;i++)
    {
    sum1+=a[pl1];
    a[pl1++]=0;
    sum2+=a[pl2];
    a[pl2--]=0;
    }
  while (pl1>0)
    {
      sum1+=a[pl1];
      a[pl1--]=0;
    }
  while (pl2<n)
    {
      sum2+=a[pl2];
      a[pl2++]=0;
    }
cout<<endl<<"sum1 = "<<sum1<<endl<<"sum2 = "<<sum2;
}

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

хм...странно...мб я оформил неправильно и отправил, поэтому ошибку выдаёт ...

Добавлено через 10 минут
n++;
1ый тест пройден, крашится на 2ом

сам код:

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
#include <iostream>
using namespace std;
int main()
{
int n;
int pl1,pl2;
cin>>n;
n++;
int *a=new int[n];
for(int i=1;i<n;i++)
  {
  cin>>a[i];
  }
cin>>pl1;
cin>>pl2;
  int sum1=0;
  int sum2=0;
  for (int i=0;pl1<pl2;i++)
    {
    sum1+=a[pl1];
    a[pl1++]=0;
    sum2+=a[pl2];
    a[pl2--]=0;
    }
  while (pl1>0)
    {
      sum1+=a[pl1];
      a[pl1--]=0;
    }
  while (pl2<n)
    {
      sum2+=a[pl2];
      a[pl2++]=0;
    }
cout<<sum1<<endl<<sum2;
}

Добавлено через 3 минуты
дурак я))
pl1 и pl2 могут быть в любом месте, да и равны по идее тоже))

Добавлено через 10 минут
всёравно крашится на 2ом тесте =((

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
using namespace std;
int main()
{
int n;
int pl1,pl2;
int sum1=0;
int sum2=0;
cin>>n;
n++;
int *a=new int[n];
for(int i=1;i<n;i++)
  {
  cin>>a[i];
  }
cin>>pl1;
cin>>pl2;
if(pl1>pl2)
  swap(pl1,pl2);
 
 
if(pl1==pl2)
  {
    int compSum1=0;
    int compSum2=0;
    for (int i=pl1;i<n;i++)
      compSum1+=a[i];
    for (int i=pl1;i>0;i--)
      compSum2+=a[i];
    if (compSum1>compSum2)
        {
        while (pl1<n)
          {
          sum1+=a[pl1];
          a[pl1++]=0;
          }
        while (pl2>0)
          {
          sum2+=a[pl2];
          a[pl2--]=0;
          }
        }
    else
        {
        while (pl1>0)
          {
            sum1+=a[pl1];
            a[pl1--]=0;
          }
        while (pl2<n)
          {
            sum2+=a[pl2];
            a[pl2++]=0;
          }
        }
 
  }
  else
    {
    while(pl1<pl2)
      {
      sum1+=a[pl1];
      a[pl1++]=0;
      sum2+=a[pl2];
      a[pl2--]=0;
      }
    while (pl1>0)
      {
        sum1+=a[pl1];
        a[pl1--]=0;
      }
    while (pl2<n)
      {
        sum2+=a[pl2];
        a[pl2++]=0;
      }
    }
cout<<sum1<<endl<<sum2;
}

Добавлено через 3 минуты
swap был лишним
решил
все тесты пройдены, я молодец, всем спасибо))

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
using namespace std;
int main()
{
int n;
int pl1,pl2;
int sum1=0;
int sum2=0;
cin>>n;
n++;
int *a=new int[n];
for(int i=1;i<n;i++)
  {
  cin>>a[i];
  }
cin>>pl1;
cin>>pl2;
 
if(pl1==pl2)
  {
    int compSum1=0;
    int compSum2=0;
    for (int i=pl1;i<n;i++)
      compSum1+=a[i];
    for (int i=pl1;i>0;i--)
      compSum2+=a[i];
    if (compSum1>compSum2)
        {
        while (pl1<n)
          {
          sum1+=a[pl1];
          a[pl1++]=0;
          }
        while (pl2>0)
          {
          sum2+=a[pl2];
          a[pl2--]=0;
          }
        }
    else
        {
        while (pl1>0)
          {
            sum1+=a[pl1];
            a[pl1--]=0;
          }
        while (pl2<n)
          {
            sum2+=a[pl2];
            a[pl2++]=0;
          }
        }
 
  }
  else
    {
      if(pl1<pl2)
        {
        while(pl1<pl2)
          {
          sum1+=a[pl1];
          a[pl1++]=0;
          sum2+=a[pl2];
          a[pl2--]=0;
          }
        while (pl1>0)
          {
            sum1+=a[pl1];
            a[pl1--]=0;
          }
        while (pl2<n)
          {
            sum2+=a[pl2];
            a[pl2++]=0;
          }
        }
        else
        {
        while(pl1>pl2)
          {
          sum1+=a[pl1];
          a[pl1--]=0;
          sum2+=a[pl2];
          a[pl2++]=0;
          }
        while (pl1<n)
          {
            sum1+=a[pl1];
            a[pl1++]=0;
          }
        while (pl2>0)
          {
            sum2+=a[pl2];
            a[pl2--]=0;
          }
        }
    }
cout<<sum1<<endl<<sum2;
}

Добавлено через 2 минуты
хотя решение и убого=(

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера 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. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041

	Найти счёт при оптимальной стратегии двух игроков 09.07.2014, 14:54. Показов 2610. Ответов 4 Метки нет (Все метки) взялся тут решать задачку с олимпиады, и честно говоря уже час потратил за зря...Никак не могу продумать сам алгоритм игры игроков... Игроки совершают ходы по очереди. На каждом ходу игрок забирает число, написанное в его текущей ячейке, затем ставит туда ноль и переходит в смежную слева или справа ячейку (разумеется, игрок не может выходить за пределы массива). Два игрока могут в некоторый момент времени находиться в одной ячейке. Счёт игрока — это сумма всех набранных во время игры чисел. Игра заканчивается, когда во всех ячейках массива записаны нули. А теперь вычислите, какое максимальное количество очков могут набрать первый и второй игроки (первый игрок, разумеется, ходит первым), если они играют оптимально, то есть стремятся максимизировать свой счёт, а если существует несколько вариантов сделать это, то стараются минимизировать счёт противника. Исходные данные: В первой строке записано целое число n — размер массива (10 ≤ n ≤ 105). Во второй строке записаны n целых чисел — исходный массив. Все элементы массива неотрицательны и не превосходят 10 000. В третьей строке записаны два целых числа — стартовые позициии первого и второго игроков соответственно. Индексация ячеек массива начинается с единицы. Результат: Выведите два числа — счёт первого и второго игроков при оптимальной игре обоих. Пример: исходные данные : 10 1 2 3 4 5 6 7 8 9 0 4 8 результат: 21 24 0

@Kukurudza 106 / 87 / 13 Регистрация: 29.08.2012 Сообщений: 538
	09.07.2014, 15:04
	может я ошибаюсь или что-то не так насчитал, но у меня получилось так: 4 8 5 9 6 0 7 1 0 2 0 3 22 и 23 соответственно а пардон, я зациклил массив видимо так нельзя 0

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041
	09.07.2014, 15:20 [ТС]
	хм... по идее главное сразу идти в сторону соперника, т.к. потом в любом случае мы идём в обратную сторону от него и он уже не успеет собрать то, что будет подбирать др игрок, т.е. игроку 1 (условно он слева) надо дойти до player2-1 позиции 2ого игрока,п осле чего бежать в обратку, соответственно 2ому аналогично... тут вопрос в другом, когда они встретятся как кому поступить лучше - уже в зав от суммы которая будет справа и слева от них 0