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

Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
05.11.2011, 15:40     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #1
Помогите пожалуйста написать 2 задачи, ребят (( Спасибо вам большое. Нужно завтра сдать, помгите пожалуйста. Буду очень признательна вам

1.Имеется n монет, разложеных на столе в один ряд. Известно достоинство каждой из монет. Два игрока по очереди берут монеты. За один ход разрешается взять крайнюю слева монету, либо крайнюю справа. Выигрывает тот, у кого в конце игры будет больше денег. Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. Счетом называется разность между суммой денег, набранной первым игроком и суммой денег, набранной вторым.

Входные данные
В первой строке находится натуральное число n (1 <= n <= 1000). В следующей строке находится n натуральных чисел, не превосходящих 10^6 - достоинства монет.

Выходные данные
Выведите единственное число - искомый счет.

Пример

Ввод
4
5 6 3 4


Вывод
2


2.На флаге имеется n разноцветных полос (1 <= n <= 1000). Цвета на различных полосах могут быть одинаковыми. Известно, что общее количество цветов на флаге не более m (1 <= m <= 100). Некоторые цвета не сочетаются друг с другом, и поэтому соседние полосы флага не могут быть раскрашены в такую пару цветов. Вам дан список таких пар. Найдите количество способов раскраски флага . На флаге не обязательно использование всех n цветов, но каждая полоса должна быть покрашена в какой-либо цвет.

Входные данные
В первой строке содержаться три натуральных числа: n, m и k, где k - количество пар не сочетающихся друг с другом цветов. В следующих k строках записано по два натуральных числа, не превосходящие n - номера цветов, которые в раскраске флага не могут находиться на соседних полосах. Каждая пара указана во входном файле не более одного раза.

Выходные данные
Выведите одно число - искомое количество способов по модулю 98759873.

Пример

Ввод
3 3 3
1 2
3 3
1 3

Вывод
6

Разъяснение
Все возможные покраски:
1 1 1
2 2 2
2 2 3
2 3 2
3 2 2
3 2 3

Cпасибо вам большое, если поможете!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2011, 15:40     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально.
Посмотрите здесь:

Каков будет порядок элементов списка[6, 2, 4, 7, 1, 3, 8, 5] после построения пирамиды C++
C++ Каков будет результат выполнения следующего кода
C++ Каков будет результат выполнения следующего кода
C++ Каков будет результат выполнения следующего кода?
Каков будет результат выполнения следующего кода C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
быдлокодер
 Аватар для быдлокодер
0 / 0 / 0
Регистрация: 23.06.2011
Сообщений: 3
05.11.2011, 16:08     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #2
Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
05.11.2011, 16:15  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #3
Цитата Сообщение от быдлокодер Посмотреть сообщение
Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать
я знаю (( пытаюсь сама разобраться, пока никак(
быдлокодер
 Аватар для быдлокодер
0 / 0 / 0
Регистрация: 23.06.2011
Сообщений: 3
05.11.2011, 16:29     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #4
пиши в асю 9070682, вместе подумаем)) я тоже над ними думаю
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2011, 16:35     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #5
По поводу первой задачи
Цитата Сообщение от Alisia Посмотреть сообщение
Пример
Ввод
4
5 6 3 4
Вывод
2
что-то здесь не так, либо задание не так звучит.
Имеем 5 6 3 4, первый берет 5, остается 6 3 4. Второй берет 6, остается 3 4. Первый берет 4, второй соответственно 3. Итого: у первого 5+4=9, у второго 6+3-9. Счет = 0.
быдлокодер
 Аватар для быдлокодер
0 / 0 / 0
Регистрация: 23.06.2011
Сообщений: 3
05.11.2011, 16:43     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #6
Цитата Сообщение от Kastaneda Посмотреть сообщение
По поводу первой задачи

что-то здесь не так, либо задание не так звучит.
Имеем 5 6 3 4, первый берет 5, остается 6 3 4. Второй берет 6, остается 3 4. Первый берет 4, второй соответственно 3. Итого: у первого 5+4=9, у второго 6+3-9. Счет = 0.
речь идет о "правильной" игре, то есть следующий ход должен принести как можно больше пользы: если первый игрок возьмет 4, то следующим ходом сможет взять 6 обеспечив себе победу
Kastaneda
05.11.2011, 16:48
  #7

Не по теме:

Цитата Сообщение от быдлокодер Посмотреть сообщение
если первый игрок возьмет 4, то следующим ходом сможет взять 6 обеспечив себе победу
А ну да, это я тупанул) А то уже подумал, что задача на олимпиадную не похожа, теперь похожа)

valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2011, 18:29     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #8
Есть такая задача:
http://********/?main=task&id_task=38
давно ее решал. Немного переделал и получилась Ваша первая задача:
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
#include <stdio.h>
int main(){
    int n, i,j, y, **mas, sum, S=0;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d",&n);
  mas=new int*[n]; 
    for(i=0; i<n; i++)
       mas[i]=new int[n];
    for(i=0; i<n; i++)
    {
        scanf("%d", &mas[i][n-1-i]);
        S+=mas[i][n-1-i];
    }
    for(i=0; i<n-1; i++)
        if(mas[i][n-1-i]>mas[i+1][n-2-i])
            mas[i][n-2-i]=mas[i][n-1-i];
        else
            mas[i][n-2-i]=mas[i+1][n-2-i];
    for(i=0; i<n-2; i++)
        for(j=0; j<n-2-i; j++)
        {
            sum=0;
            for(y=0; y<i+3; y++)
                sum+=mas[y+j][n-1-y-j];
            if(mas[j][n-2-i-j]>mas[j+1][n-3-i-j])
                mas[j][n-3-i-j]=sum-mas[j+1][n-3-i-j];
            else
                mas[j][n-3-i-j]=sum-mas[j][n-2-i-j];
        }
    printf("%d", mas[0][0]*2-S);
  
  return 0;
}
Mиxaил
 Аватар для Mиxaил
530 / 435 / 37
Регистрация: 10.12.2009
Сообщений: 1,857
05.11.2011, 18:34     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #9
Тут, случайно, не рекурсией делать нужно?! Необходимо ведь выбрать наиболее оптимальный расчет монет с учетом последующих выборов...
LMapper
9 / 9 / 0
Регистрация: 27.09.2011
Сообщений: 97
05.11.2011, 19:16     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #10
Ребят, какой класс ?
Округ ?
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
06.11.2011, 01:02     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #11
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Есть такая задача:
http://********/?main=task&id_task=38
давно ее решал. Немного переделал и получилась Ваша первая задача:
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
#include <stdio.h>
int main(){
    int n, i,j, y, **mas, sum, S=0;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d",&n);
  mas=new int*[n]; 
    for(i=0; i<n; i++)
       mas[i]=new int[n];
    for(i=0; i<n; i++)
    {
        scanf("%d", &mas[i][n-1-i]);
        S+=mas[i][n-1-i];
    }
    for(i=0; i<n-1; i++)
        if(mas[i][n-1-i]>mas[i+1][n-2-i])
            mas[i][n-2-i]=mas[i][n-1-i];
        else
            mas[i][n-2-i]=mas[i+1][n-2-i];
    for(i=0; i<n-2; i++)
        for(j=0; j<n-2-i; j++)
        {
            sum=0;
            for(y=0; y<i+3; y++)
                sum+=mas[y+j][n-1-y-j];
            if(mas[j][n-2-i-j]>mas[j+1][n-3-i-j])
                mas[j][n-3-i-j]=sum-mas[j+1][n-3-i-j];
            else
                mas[j][n-3-i-j]=sum-mas[j][n-2-i-j];
        }
    printf("%d", mas[0][0]*2-S);
  
  return 0;
}
Как же вы умудрились это решение запихать в TimeLimit? за O(n^3) работает
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.11.2011, 07:53     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #12
Цитата Сообщение от Shato Посмотреть сообщение
Как же вы умудрились это решение запихать в TimeLimit? за O(n^3) работает
то была немного другая задача (ограничения чуть меньше) и все тесты по времени прошла. Кстати и для этой задачи тестирую, тоже работает довольно быстро. Ошибка тех кто писал условия этой задачи и подобных - не указываете ограничения по времени.
Ладно, вот вам тогда другой вариант 1-ой задачи, побыстрее:
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
#include <stdio.h>
int mas[1000][1000], S=0;
int a[1000];
int rec(int x, int y, int S)
{
    if(mas[x][y])
        return mas[x][y];
    if(x==y)
        return a[x];
    int t1, t2;
    if(mas[x+1][y])
        t1=S-mas[x+1][y];
    else
        t1=S-rec(x+1, y, S-a[x]);
    if(mas[x][y-1])
        t2=S-mas[x][y-1];
    else
        t2=S-rec(x, y-1, S-a[y]);
    if(t1>t2)
    {
        mas[x][y]=t1;
        return t1;
    }
    mas[x][y]=t2;
    return t2;
}
int main(){
    int n, i;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d",&n);
  for(i=0; i<n; i++)
  {
      scanf("%d", &a[i]);
      S+=a[i];
  }
  int res=rec(0, n-1, S);
  printf("%d", res*2-S);  
  return 0;
}
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
06.11.2011, 21:53  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
то была немного другая задача (ограничения чуть меньше) и все тесты по времени прошла. Кстати и для этой задачи тестирую, тоже работает довольно быстро. Ошибка тех кто писал условия этой задачи и подобных - не указываете ограничения по времени.
Ладно, вот вам тогда другой вариант 1-ой задачи, побыстрее:
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
#include <stdio.h>
int mas[1000][1000], S=0;
int a[1000];
int rec(int x, int y, int S)
{
    if(mas[x][y])
        return mas[x][y];
    if(x==y)
        return a[x];
    int t1, t2;
    if(mas[x+1][y])
        t1=S-mas[x+1][y];
    else
        t1=S-rec(x+1, y, S-a[x]);
    if(mas[x][y-1])
        t2=S-mas[x][y-1];
    else
        t2=S-rec(x, y-1, S-a[y]);
    if(t1>t2)
    {
        mas[x][y]=t1;
        return t1;
    }
    mas[x][y]=t2;
    return t2;
}
int main(){
    int n, i;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d",&n);
  for(i=0; i<n; i++)
  {
      scanf("%d", &a[i]);
      S+=a[i];
  }
  int res=rec(0, n-1, S);
  printf("%d", res*2-S);  
  return 0;
}
Cпасибо огромное, а первая сложная?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.11.2011, 22:08     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #14
Цитата Сообщение от Alisia Посмотреть сообщение
Cпасибо огромное, а первая сложная?
это и была первая.
вторая тоже не сложная.
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
06.11.2011, 22:12  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #15
Цитата Сообщение от valeriikozlov Посмотреть сообщение
это и была первая.
вторая тоже не сложная.
не займет много времени?
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 00:52     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #16
Цитата Сообщение от Alisia Посмотреть сообщение
не займет много времени?
да время то точно много не займет))))
LMapper
9 / 9 / 0
Регистрация: 27.09.2011
Сообщений: 97
07.11.2011, 00:54     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #17
Цитата Сообщение от Montanaa Посмотреть сообщение
да время то точно много не займет))))
Это был намёк
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 01:09     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #18
Цитата Сообщение от LMapper Посмотреть сообщение
Это был намёк
да я понял =)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2011, 06:03     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #19
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 "stdio.h"
int main()
{
 
    int n, m , k, mas_res[100][1000], i, j, mod=98759873, res=0, y;
    bool sm[100][100];
    for(i=0; i<100; i++)
    {
        for(j=0; j<100; j++)
            sm[i][j]=false;
        for(j=0; j<1000; j++)
            mas_res[i][j]=0;
    }
    scanf("%d %d %d", &n, &m, &k);
    while(k>0)
    {
        scanf("%d %d", &i, &j);
        sm[i-1][j-1]=sm[j-1][i-1]=true;
        k--;
    }
    for(i=0; i<n; i++)
        mas_res[i][0]=1;
    for(i=1; i<m; i++)
    {
        for(j=0; j<n; j++)
            for(y=0; y<n; y++)
                if(!sm[j][y])
                    mas_res[y][i]+=mas_res[j][i-1];
        for(j=0; j<n; j++)
            mas_res[j][i]%=mod;
    }
    for(i=0; i<n; i++)
        res+=mas_res[i][m-1];
    printf("%d", res%mod);  
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2011, 08:56     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально.
Еще ссылки по теме:

C++ Каков будет результат выполнения следующего кода?
Вывести первое число, если оно больше второго, и оба числа, если это не так C++
C++ Как записать статистику игры (победы компьютера, игрока и ничью) в txt-файл?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
07.11.2011, 08:56  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
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 "stdio.h"
int main()
{
 
    int n, m , k, mas_res[100][1000], i, j, mod=98759873, res=0, y;
    bool sm[100][100];
    for(i=0; i<100; i++)
    {
        for(j=0; j<100; j++)
            sm[i][j]=false;
        for(j=0; j<1000; j++)
            mas_res[i][j]=0;
    }
    scanf("%d %d %d", &n, &m, &k);
    while(k>0)
    {
        scanf("%d %d", &i, &j);
        sm[i-1][j-1]=sm[j-1][i-1]=true;
        k--;
    }
    for(i=0; i<n; i++)
        mas_res[i][0]=1;
    for(i=1; i<m; i++)
    {
        for(j=0; j<n; j++)
            for(y=0; y<n; y++)
                if(!sm[j][y])
                    mas_res[y][i]+=mas_res[j][i-1];
        for(j=0; j<n; j++)
            mas_res[j][i]%=mod;
    }
    for(i=0; i<n; i++)
        res+=mas_res[i][m-1];
    printf("%d", res%mod);  
    return 0;
}
вроде бы не верные результаты
Yandex
Объявления
07.11.2011, 08:56     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально.
Ответ Создать тему
Опции темы

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