Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 08:58     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #21
Цитата Сообщение от 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;
}
да и тут он должен выходить за границцы массива. я не прав?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
07.11.2011, 14:47  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #22
Цитата Сообщение от Montanaa Посмотреть сообщение
да и тут он должен выходить за границцы массива. я не прав?
не должен
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 17:43     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #23
Цитата Сообщение от Alisia Посмотреть сообщение
не должен
поясните
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2011, 17:49     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #24
Цитата Сообщение от Alisia Посмотреть сообщение
вроде бы не верные результаты
на чем основан вывод?
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
07.11.2011, 17:52  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #25
Цитата Сообщение от valeriikozlov Посмотреть сообщение
на чем основан вывод?
на тестах
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2011, 18:32     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #26
Цитата Сообщение от Alisia Посмотреть сообщение
на тестах
есть какой-нибудь тест из не пройденных?

Добавлено через 19 минут
Долго нет ответа (а зря, быстрее получилось бы найти ошибку). Вот так пробуйте:
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 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];
                                        mas_res[y][i]%=mod;
                                }
        }
for(i=0; i<n; i++)
{
 res+=mas_res[i][m-1];
 res%=mod;
}
 printf("%d", res); 
 return 0;   
}
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 19:40     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #27
Цитата Сообщение от valeriikozlov Посмотреть сообщение
есть какой-нибудь тест из не пройденных?

Добавлено через 19 минут
Долго нет ответа (а зря, быстрее получилось бы найти ошибку). Вот так пробуйте:
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 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];
                                        mas_res[y][i]%=mod;
                                }
        }
for(i=0; i<n; i++)
{
 res+=mas_res[i][m-1];
 res%=mod;
}
 printf("%d", res); 
 return 0;   
}
а, ошибся.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2011, 19:50     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #28
Цитата Сообщение от Montanaa Посмотреть сообщение
А тут разве не нужно каждый раз считать по модулю? с заданным числом. А не только ответ. мб я не прав
нужно, и это сделано.
смотри строку 30 в моем коде.
То что эта строка "зашкалила", претензии к оформлению форума (но можно было и внимательнее посмотреть).
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 19:52     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #29
Цитата Сообщение от valeriikozlov Посмотреть сообщение
нужно, и это сделано.
смотри строку 30 в моем коде.
То что эта строка "зашкалила", претензии к оформлению форума (но можно было и внимательнее посмотреть).
я извиняюсь, уже заметил
Alisia
 Аватар для Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
07.11.2011, 19:56  [ТС]     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #30
Цитата Сообщение от valeriikozlov Посмотреть сообщение
нужно, и это сделано.
смотри строку 30 в моем коде.
То что эта строка "зашкалила", претензии к оформлению форума (но можно было и внимательнее посмотреть).
я пробовала так делать, не получается (

Добавлено через 3 минуты
Цитата Сообщение от valeriikozlov Посмотреть сообщение
нужно, и это сделано.
смотри строку 30 в моем коде.
То что эта строка "зашкалила", претензии к оформлению форума (но можно было и внимательнее посмотреть).
у меня вам личные сообщения не отправляются (
тестов проходит 2 или 3. в основном пишет, что или не правильный ответ на тест или ошибка времени исполнения
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2011, 19:56     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально.
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2011, 19:56     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. #31
Alisia, ссылку на тестирующую систему можете дать?
Yandex
Объявления
07.11.2011, 19:56     Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально.
Ответ Создать тему
Опции темы

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