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

Задача «Футбол» - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Includenv
Сообщений: n/a
20.10.2011, 14:50     Задача «Футбол» #1
Добрый день. Никак не могу придумать, как решить данную задачу с помощью динамического программирования.

Условие:
Олег — большой любитель футбола и статистики. Недавно он нашел результаты участия его любимой команды в каком-то давнем чемпионате. К сожалению, единственной сохранившейся информацией оказалось то, сколько матчей было сыграно и сколько очков набрала команда. Напоминаем, что если матч завершается победой команды, то ей присуждается три очка, ничьей — одно очко, и если команда проигрывает матч, то она не получает ни одного очка.

Олегу стало интересно, сколько различных вариантов прохождения чемпионата было у его любимой команды. Различными считаются варианты, если результат хотя бы одного матча различен, причем счет не принимается во внимание, а учитывается только то, завершился матч победой, ничьей или проигрышем.

Формат входных данных
Первая строка входного файла содержит два целых числа: n_ (0 ≤ _n ≤ 36) — количество набранных командой очков, и k_ (1 ≤ _k ≤ 12) — количество матчей, сыгранных этой командой в чемпионате.

Формат выходных данных
В выходной файл выведите число различных вариантов прохождения чемпионата любимой команды Олега.

Примеры:
InputOutput
3 22
4 36
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2011, 14:50     Задача «Футбол»
Посмотрите здесь:

Футбол. Какая команда покинет высшую лигу? сделате! C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.10.2011, 19:03     Задача «Футбол» #2
Цитата Сообщение от Includenv Посмотреть сообщение
Никак не могу придумать, как решить данную задачу с помощью динамического программирования.
код писать не буду, но алгоритм решения напишу:
заводим массив mas[k], внутри которого каждый элемент представляет собой массив mas1[n+1]. Хотите делайте это с помощью двумерного массива, можете с помощью структур.
В mas[0] заполняем вручную mas1[n+1] так: mas1[0]=1 (это значит, что в первом матче кол-во вариантов проигрыша равно 1), mas1[1]=1 (кол-во вариантов в первом матче ничьи равно 1) и mas1[3]=1 (кол-во вариантов в первом матче выигрыша равно 1). Остальные элементы mas1[] в mas[0] равны 0. (Но и здесь уже нужно учитывать возможность выхода из границ массива mas1[] - ведь n может быть равно даже 0).
Можно уже на этом этапе все элементы mas1[] во всех элементах mas[1...n-1] обнулить.
Затем сама динамика:
перебираем элементы mas[i] по порядку. Для каждого mas[i] заполняем mas1[n+1] учитывая значения mas1[n+1] предыдущего mas[i-1]. Т.е. перебираем значения mas1[j] элемента mas[i-1] и если оно не равно 0, то (из этого состояния могли выиграть +3, ничья +1, проиграть +0) прибавляем это значение к mas1[j+3] (элемента mas[i]), к mas1[j+1] (элемента mas[i]), к mas1[j] (элемента mas[i]). (естественно учитываем границы массива mas1[] элемента mas[i]).
По окончании такого прохода результат будет находится в mas[n], в mas1[k].
Includenv
Сообщений: n/a
21.10.2011, 15:22     Задача «Футбол» #3
Код и не надо было писать. Это было бы слишком.
Спасибо, сегодня попробую реализовать.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2011, 15:52     Задача «Футбол» #4
Цитата Сообщение от Includenv Посмотреть сообщение
Код и не надо было писать. Это было бы слишком.
Вообще-то, код даже проще было написать. Если что не получится, обращайтесь.
Includenv
Сообщений: n/a
22.10.2011, 14:05     Задача «Футбол» #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вообще-то, код даже проще было написать. Если что не получится, обращайтесь.
Спасибо. Всё получилось.
Yandex
Объявления
22.10.2011, 14:05     Задача «Футбол»
Ответ Создать тему
Опции темы

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