Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа N и w, а за ними следует последовательность
из N целых чисел ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами.
Единица на позиции i означает, что элемент последовательности ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите −1.
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами,
N — количество достоинств монет,
Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа EFN.
В следующих N строках находятся по два числа — CiWi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число −1.
Ограничения
1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100
1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1
Задача C. Наибольшая возрастающая подпоследовательность
≡
The main hall of the Nearsea Institute of Unspecified Underwater Studies
has a shape of a long corridor.
Along the corridor, there are N aquariums exhibiting various
sea creatures. Aquariums are located at distances x1, …, xN
from the hall entrance (xi < xi + 1).
The institute has recently got a new director, who decided that
the aquarium maintenance is too costly, and issued an order to remove
M (0 ≤ M ≤ N − 2) aquariums.
To minimize the disruption to the looks of the hall, it was decided that:
the first and the last aquariums should be left in their places;
the maximum distance between the adjacent aquariums must be as small as possible.
Your program must select aquariums for removal in such a way that the above conditions are
satisfied.
Input file format
Input file contains integers NM followed by N integers xi.
Output file format
Output file should contain a single integer — the smallest possible maximum distance.
N delegations arrived for the ACM ICPC quarterfinals. Delegation i consists of ai people.
The organizers were able to find M buses to deliver the contestants from the hotel to the
university. Bus j has enough place for bj people.
Settling the delegations into buses was entrusted to Masha — the most responsible member of the
organizing committee. However, that was done in the very last day, which resulted in the following:
The buses will arrive in a particular order which Masha can't control.
Each bus leaves before the next one arrives.
Delegations will queue at the bus stop in a particular order that Masha can't control.
A delegation may start to take seats only after all delegations in front
of it in the queue are seated.
Contestants from each delegation prefer to stay together. But unfortunately some delegations may
have to split into groups to fit into the buses. Masha wants to help
the teams to form the least number of groups that will fit in the buses, given the constraints above
(if a delegation is not split, it counts as 1 group).
Your program must allocate bus seats to contestants in a way which minimizes
number of groups. It's guaranteed that total amount of people is not more than total
capacity of the buses.
Input file format
Input file contains an integer N — number of delegations,
followed by N integers ai — sizes of delegations in the order they queue at the
bus stop.
Further follows an integer M — number of buses, followed by M integers bj —
capacities of the buses in the order they arrive.
Output file format
Output file must contain a description for each delegation from 1 to N, in the same order as input.
A description for delegation i starts with a positive integer pi — the number of groups that
the delegation is split into (1 means the delegation is not split at all).
Further, pi pairs of positive integers must follow. The first integer of each pair is the
number of the bus that the group should take (buses are numbered from 1 to M).
The second integer is the size of the group.
Groups within one delegation should be described in the order of ascending bus numbers.
The number of groups in the output should be minimal possible, given the constrains above.
If there is more than one optimal solution, output any of them.
In the sample test #1 there are 3 delegations and 2 buses. The answer contains 4 groups in total
(we have to split delegation 2 into 2 groups).
In the sample test #2 the second bus can fit both delegations, no splits required. Note that the
first bus leaves completely empty.
