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

@Alisia · Регистрация: 05.11.2011

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста написать 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пасибо вам большое, если поможете!

@быдлокодер · 05.11.2011, 16:08

Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать

@Alisia · 05.11.2011, 16:15 **[ТС]**

Сообщение от быдлокодер

Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно)))
З.Ы. мир(интернет) тесен))
З.З.Ы. задачи надо до четверга сделать

я знаю (( пытаюсь сама разобраться, пока никак(

@быдлокодер · 05.11.2011, 16:29

пиши в асю 9070682, вместе подумаем)) я тоже над ними думаю

@Kastaneda · 05.11.2011, 16:35

По поводу первой задачи

Сообщение от 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.

@быдлокодер · 05.11.2011, 16:43

Сообщение от 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

Не по теме:

Сообщение от быдлокодер

если первый игрок возьмет 4, то следующим ходом сможет взять 6 обеспечив себе победу

А ну да, это я тупанул) А то уже подумал, что задача на олимпиадную не похожа, теперь похожа)

valeriikozlov · 05.11.2011, 18:29

Есть такая задача:
http://acmp.ru/?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ил · 05.11.2011, 18:34

Тут, случайно, не рекурсией делать нужно?! Необходимо ведь выбрать наиболее оптимальный расчет монет с учетом последующих выборов...

@LMapper · 05.11.2011, 19:16

Ребят, какой класс ?
Округ ?

@Shato · 06.11.2011, 01:02

Сообщение от valeriikozlov

Есть такая задача:
http://acmp.ru/?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 · 06.11.2011, 07:53

Сообщение от 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 · 06.11.2011, 21:53 **[ТС]**

Сообщение от 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 · 06.11.2011, 22:08

Сообщение от Alisia

Cпасибо огромное, а первая сложная?

это и была первая.
вторая тоже не сложная.

@Alisia · 06.11.2011, 22:12 **[ТС]**

Сообщение от valeriikozlov

это и была первая.
вторая тоже не сложная.

не займет много времени?

@Montanaa · 07.11.2011, 00:52

Сообщение от Alisia

не займет много времени?

да время то точно много не займет))))

@LMapper · 07.11.2011, 00:54

Сообщение от Montanaa

да время то точно много не займет))))

Это был намёк

@Montanaa · 07.11.2011, 01:09

Сообщение от LMapper

Это был намёк

да я понял =)

valeriikozlov · 07.11.2011, 06:03

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 · 07.11.2011, 08:56 **[ТС]**

Сообщение от 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;
}

вроде бы не верные результаты

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Alisia 0 / 0 / 0 Регистрация: 05.11.2011 Сообщений: 23

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

@быдлокодер 0 / 0 / 0 Регистрация: 23.06.2011 Сообщений: 3
	05.11.2011, 16:08
	Alisia, домашнее задание в центре олимпиадной подготовки дают чтобы его делали самостоятельно))) З.Ы. мир(интернет) тесен)) З.З.Ы. задачи надо до четверга сделать 0

@быдлокодер 0 / 0 / 0 Регистрация: 23.06.2011 Сообщений: 3
	05.11.2011, 16:29
	пиши в асю 9070682, вместе подумаем)) я тоже над ними думаю 0

@Mиxaил 542 / 447 / 162 Регистрация: 10.12.2009 Сообщений: 1,857
	05.11.2011, 18:34
	Тут, случайно, не рекурсией делать нужно?! Необходимо ведь выбрать наиболее оптимальный расчет монет с учетом последующих выборов... 0

@LMapper 9 / 9 / 0 Регистрация: 27.09.2011 Сообщений: 97
	05.11.2011, 19:16
	Ребят, какой класс ? Округ ? 0