Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Ход конем_1

Динамическое программирование

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).
 
 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
 
Входные данные
В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 50).  
 
Выходные данные
В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски.

Ввод Вывод
4 4 2

Лесопилка

Динамическое программирование

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.
 
Поскольку на лесопилке имеется только неограниченный запас досок длины z футов, Васе поручили исполнить заказ клиента, распилив имеющиеся доски на меньшие. Вася хочет закончить работу как можно быстрее, поэтому он хочет выполнить заказ, сделав как можно меньше распилов. При этом количество использованных досок длины z роли не играет, кроме того, часть досок, образовавшихся в результате распила, может не требоваться для заказа и остаться на лесопилке.
 
Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.
 
Входные данные
На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.
 
Выходные данные
Выведите  минимальное количество распилов, которые требуется сделать для того, чтобы выполнить заказ.

Ввод Вывод
2 30 7 20 80 7

 

87. Максимальная сумма смежных элементов

Динамическое программирование

На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальную сумму смежных элементов последовательности. N не превышает 1000000, каждый элемент последовательности не превосходит по модулю 100.

Ввод Вывод
9
-2
1
-3
4
-1
2
1
-5
4
6

 
Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.
Решение на 2 балла проходит 50% тестов, на 3 балла 75%.
(с) Жуков
 

Сборка компьютера

Динамическое программирование

Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.
Напишите программу, определяющую из каких компонентов нужно собрать компьютер, чтобы его стоимость не превышала B, в составе были по одному компоненту каждого типа, а суммарный рейтинг использованных компонентов был максимальным.

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента Ci (1 ≤ Ci ≤ 3000), его рейтинг Ri (1 ≤ Ri ≤ 3000) и его тип ti (1 ≤ ti ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод Вывод
2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16
18
2 5

Ход конем - 2

Динамическое программирование

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:



Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные
В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15).  
 
Выходные данные
В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски.

Ввод Вывод
4 4 2
7 15 13309