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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Alisia
0 / 0 / 0
Регистрация: 05.11.2011
Сообщений: 23
#1

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

05.11.2011, 15:40. Просмотров 1926. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Спрашивается, каков будет счет в конце игры, если оба игрока действуют оптимально. (C++):

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

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

Что будет выводить puts, если в конце строки не будет нулевого байта - C (СИ)
что будет выводить puts, если в конце строки не будет нулевого байта

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

Морской бой. Оба игрока компьютер - Delphi
Вопрос состоит в том, как реализовать Морской бой, когда оба игрока компьютер. С распараллеливанием через подключение MPI или эмуляцией...

Если оба числа четные, то оба возвестив квадрат - Pascal ABC
Даны 2 вещественных числа, если они оба четные то оба возвестив квадрат, если нет то к каждому из них прибавить 3. uses crt; var...

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
Нарушитель
Эксперт С++
4671 / 2875 / 233
Регистрация: 12.12.2009
Сообщений: 7,308
Записей в блоге: 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
Эксперт С++
4670 / 2496 / 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;
}
1
Mиxaил
533 / 438 / 37
Регистрация: 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 / 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) работает
1
valeriikozlov
Эксперт С++
4670 / 2496 / 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;
}
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
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
06.11.2011, 22:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2011, 22:12
Привет! Вот еще темы с ответами:

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

Оптимально ли будет? - Рабочая станция
DDR-3 DIMM 8Gb/1600MHz PC12800 Kingston HyperX, 2х4Gb Kit, BOX Блок питания ATX 850W Thermaltake TRX-850M Жесткий диск SSD 120 Gb...

какую модель будет оптимально взять за 30 000 - Ноутбуки
Хочу купить ноутбук!! Парни подскажите Очень прошу написать Вас какую модель будет оптимально взять за 30 000 ...и почему ...

Вывести первое число, если оно больше второго, и оба числа, если это не так - Turbo Pascal
Здравствуйте всем, я начинающий программист... :) Помогите, пожалуйста, кто сможет, решаю контрольную работу по турбо паскалю (заодно...


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

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

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