Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
09.07.2014, 14:54     Найти счёт при оптимальной стратегии двух игроков #1
взялся тут решать задачку с олимпиады, и честно говоря уже час потратил за зря...Никак не могу продумать сам алгоритм игры игроков...

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

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

Результат:
Выведите два числа — счёт первого и второго игроков при оптимальной игре обоих.
Пример:
исходные данные :
10
1 2 3 4 5 6 7 8 9 0
4 8
результат:
21 24
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2014, 14:54     Найти счёт при оптимальной стратегии двух игроков
Посмотрите здесь:

C++ Среди чисел найти все, у которых сумма первых двух равна сумме последних двух
C++ Смоделировать бросание каждым из двух игроков трех игральных кубиков
Стратегии обслуживания жесткого диска C++
C++ Осуществить конкатенацию двух файлов за счёт создания третьего файла (Маленькая доработка)
Оптимизация за счёт устранения временных объектов при использовании операторов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2014, 15:04     Найти счёт при оптимальной стратегии двух игроков #2
может я ошибаюсь или что-то не так насчитал, но у меня получилось так:
4 8
5 9
6 0
7 1
0 2
0 3
22 и 23 соответственно
а пардон, я зациклил массив видимо так нельзя
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
09.07.2014, 15:20  [ТС]     Найти счёт при оптимальной стратегии двух игроков #3
хм... по идее главное сразу идти в сторону соперника, т.к. потом в любом случае мы идём в обратную сторону от него и он уже не успеет собрать то, что будет подбирать др игрок, т.е. игроку 1 (условно он слева) надо дойти до player2-1 позиции 2ого игрока,п осле чего бежать в обратку, соответственно 2ому аналогично...

тут вопрос в другом, когда они встретятся как кому поступить лучше - уже в зав от суммы которая будет справа и слева от них
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.07.2014, 15:33     Найти счёт при оптимальной стратегии двух игроков #4
Цитата Сообщение от 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
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
09.07.2014, 16:23  [ТС]     Найти счёт при оптимальной стратегии двух игроков #5
Цитата Сообщение от 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 минуты
хотя решение и убого=(
Yandex
Объявления
09.07.2014, 16:23     Найти счёт при оптимальной стратегии двух игроков
Ответ Создать тему
Опции темы

Текущее время: 20:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru