Все задачи

Фирма "All Colors Mixing" предлагает большой ассортимент красок по каталогу. Чтобы не хранить много красок в каждом магазине, большинство красок изготавливается на месте при поступлении заказа путем смешивания из нескольких базовых красок. Пропорция красок, необходимая для получения нужного оттенка, указывается в каталоге. Например, для получения сиреневой краски нужно смешать красную, синюю и белую краски в пропорции 1:2:3. Аппарат для смешивания красок может отмерять только выражаемые целыми числами объемы базовых красок. Поэтому, если покупателю необходимо 10 мл сиреневой краски, необходимо изготовить 12 мл краски, смешав 2 мл красной, 4 мл синей и 6 мл белой краски.

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 5`) – количество базовых красок для получения нужного цвета. Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до 1000, разделенных пробелами – пропорция смешивания базовых красок. Третья строка содержит одно целое число `V` (`10\ ≤\ V\ <\ 10^9`) – количество краски, необходимое покупателю.

Вывести одно целое число – минимальное количество краски, которое нужно изготовить для выполнения заказа покупателя.

3
1 2 3
10

12

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

Напишите программу, определяющую, как нужно расставить машины.

В первой строке ввода содержатся два целых числа – количество различных типов машин `N` (`1\ ≤\ N\ ≤\ 5`) и число рядов `M` (`1\ ≤\ M\ ≤\ 20`). Во второй строке содержатся `N` целых положительных чисел, разделенных пробелами – количества машин каждого типа. Общее количество машин не превышает 100. В третьей строке содержатся `N` целых чисел, разделенных пробелами – длины машин каждого типа в диапазоне от 1 до `10^5`.

Вывести `M` строк, содержащих по `N` чисел – для каждого ряда указывается число машин каждого типа, поставленных в соответствующий ряд. Можно вывести любое из решений, удовлетворяющее условиям. Если размещение коллекции в `M` рядов одинаковой длины невозможно, вывести сообщение "IMPOSSIBLE".

3 2
2 3 2
15 10 7

2 0 1
0 3 1

Король Флатландии решил направить свою страну по пути научно-технического прогресса и повелел построить `K` железных дорог таким образом, чтобы из любого города страны можно было проехать до любого другого по железной дороге прямо или с пересадками через другие города. Железнодорожные компании, заинтересованные в финансировании, предложили министру транспорта откат в случае принятия их предложений. Хитрый министр решил построить дороги таким образом, чтобы не только обеспечить выполнение приказа короля, но и получить максимальный доход.

В первой строке ввода содержатся три целых числа, разделенных пробелами – количество городов в стране `N` (`1\ <\ N\ ≤\ 30000`), число предложений от компаний `M` (`N-1\ ≤\ M\ ≤\ 10^5`) и количество дорог `K` (`N-1\ ≤\ K\ ≤\ M`). Далее следует `M` строк, содержащих по три целых числа – номера городов `a_i` и `b_i` (`1\ ≤\ a_i\ <\ b_i\ ≤\ N`), между которыми предлагается построить дорогу, и величина отката `c_i` (`0\ ≤\ c_i\ ≤\ 10^9`). Пары городов в списке предложений не повторяются.

Вывести одно целое число – максимальный доход министра. Если выполнить приказ короля невозможно, вывести число `-1`.

4 6 5
1 2 200
1 3 100
1 4 150
2 3 90
2 4 180
3 4 120

750