Подразделы

Другие разделы

Дата и время

13/03/2025 13:24:58

Авторизация

Задачи командного чемпионата

1. Малыш и Карлсон 2. Треугольники 3. Комментарии 4. Divide by Squares 5. Плотность населения 6. Контрольная сумма 7. Газовые войны 8. Задача Пифагора 9. The Picture Drawing

7. Газовые войны

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Газовая компания должна поставлять потребителям определенный контрактами объем газа, но при транспортировке газ может откачиваться из трубы и в результате потребители могут не получить газ в нужном объеме.

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

Первая строка входного файла содержит три целых числа, разделенных пробелами – количество потребителей

$N$ (

$1\ ≤\ N\ ≤\ 10$ ), количество промежуточных насосных станций

$K$ (

$0\ ≤\ K\ ≤\ 100$ ) и количество труб для транспортировки газа

$M$ (

$1\ ≤\ M\ ≤\ 1000$ ). Вторая строка содержит

$N$ целых чисел

$V_i$ (

$0\ <\ V_j\ ≤\ 100$ ), разделенных пробелами – объемы газа, которые необходимо поставить потребителям. Далее следует

$M$ строк, содержащих по четыре целых числа, разделенных пробелами – номера узлов

$a_j$ (

$0\ ≤\ a_j\ ≤\ K+N$ ) и

$b_j$ (

$0\ ≤\ b_j\ ≤\ K+N$ ), связанных трубой, максимальный объем газа

$f_j$ (

$0\ <\ f_j\ ≤\ 100$ ), который можно подать на вход этой трубы и процент газа

$d_j$ (

$0\ ≤\ d_j\ ≤\ 100$ ), который выкачивается из этой трубы при транспортировке. Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до

$N$ . Промежуточные насосные станции имеют номера от

$N+1$ до

$N+K$ . Между двумя узлами проходит не более одной трубы.

В выходной файл вывести одно число – минимальный объем поставок газа для обеспечения всех потребителей с точностью

$10^{-5}$ . Если для какого-нибудь из потребителей невозможно выполнить поставку в требуемом объеме, то вывести число

$-1$ .

Пример ввода

Вывод для примера

11.21875