Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
1

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

05.11.2011, 15:40. Просмотров 2024. Ответов 30
Метки нет (Все метки)

Помогите пожалуйста написать 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пасибо вам большое, если поможете!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2011, 15:40
Ответы с готовыми решениями:

Зная квалификацию игроков определить общее число подтягиваний, которое совершат оба игрока за время игры
Пусть квалификация первого игрока равна A, а квалификация второго равна B....

Каков будет ток в конце десятой секунды, если в начале опыта был 16 и 2/3 А?
Нужна помощь в решении задачи! &quot;Разность потенциалов на зажимах катушки...

Что будет выводить puts, если в конце строки не будет нулевого байта
что будет выводить puts, если в конце строки не будет нулевого байта

Каков шанс получить пожар в квартире если будет у меня системника работать сутками?
Сорри не знал куда написать, но напишу сюда. Если что не так заранее извиняюсь...

Каков будет результат выполнения операции сцепления строк, если длина результирующей строки превысит значение 255
Каков будет результат выполнения операции сцепления строк, если длина...

30
быдлокодер
0 / 0 / 0
Регистрация: 23.06.2011
Сообщений: 3
05.11.2011, 16:08 2
Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать
0
Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
05.11.2011, 16:15  [ТС] 3
Цитата Сообщение от быдлокодер Посмотреть сообщение
Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать
я знаю (( пытаюсь сама разобраться, пока никак(
0
быдлокодер
0 / 0 / 0
Регистрация: 23.06.2011
Сообщений: 3
05.11.2011, 16:29 4
пиши в асю 9070682, вместе подумаем)) я тоже над ними думаю
0
Kastaneda
Jesus loves me
Эксперт С++
4940 / 3017 / 346
Регистрация: 12.12.2009
Сообщений: 7,612
Записей в блоге: 2
Завершенные тесты: 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 / 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 обеспечив себе победу
0
Kastaneda
05.11.2011, 16:48
  #7

Не по теме:

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

0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2011, 18:29 8
Есть такая задача:

давно ее решал. Немного переделал и получилась Ваша первая задача:
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;
}
1
Mиxaил
534 / 439 / 162
Регистрация: 10.12.2009
Сообщений: 1,857
05.11.2011, 18:34 9
Тут, случайно, не рекурсией делать нужно?! Необходимо ведь выбрать наиболее оптимальный расчет монет с учетом последующих выборов...
0
LMapper
9 / 9 / 0
Регистрация: 27.09.2011
Сообщений: 97
05.11.2011, 19:16 10
Ребят, какой класс ?
Округ ?
0
Shato
2 / 2 / 1
Регистрация: 16.03.2011
Сообщений: 82
06.11.2011, 01:02 11
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Есть такая задача:

давно ее решал. Немного переделал и получилась Ваша первая задача:
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) работает
1
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 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;
}
1
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пасибо огромное, а первая сложная?
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
06.11.2011, 22:08 14
Цитата Сообщение от Alisia Посмотреть сообщение
Cпасибо огромное, а первая сложная?
это и была первая.
вторая тоже не сложная.
0
Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
06.11.2011, 22:12  [ТС] 15
Цитата Сообщение от valeriikozlov Посмотреть сообщение
это и была первая.
вторая тоже не сложная.
не займет много времени?
0
Montanaa
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 00:52 16
Цитата Сообщение от Alisia Посмотреть сообщение
не займет много времени?
да время то точно много не займет))))
0
LMapper
9 / 9 / 0
Регистрация: 27.09.2011
Сообщений: 97
07.11.2011, 00:54 17
Цитата Сообщение от Montanaa Посмотреть сообщение
да время то точно много не займет))))
Это был намёк
0
Montanaa
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
07.11.2011, 01:09 18
Цитата Сообщение от LMapper Посмотреть сообщение
Это был намёк
да я понял =)
0
valeriikozlov
Эксперт С++
4686 / 2512 / 751
Регистрация: 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;
}
1
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;
}
вроде бы не верные результаты
0
07.11.2011, 08:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2011, 08:56

Морской бой. Оба игрока компьютер
Вопрос состоит в том, как реализовать Морской бой, когда оба игрока компьютер....

Если оба числа четные, то оба возвестив квадрат
Даны 2 вещественных числа, если они оба четные то оба возвестив квадрат, если...

Если открыть .exe от игры будет ли доступность модифицыровать её?
Доброго времени суток. Скрыл .exe с помощью Дизассемблером возможно ли...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru