| Central Russia Regional Contest, 2022 |
|---|
| Закончено |
Существует достаточно много головоломок, в которых нужно отмерить определенный интервал времени с помощью неравномерно горящих бикфордовых (огнепроводных) шнуров. Например, с помощью шнура, который целиком сгорает за $$$1$$$ минуту, можно легко отмерить $$$30$$$ секунд – для этого нужно просто поджечь этот шнур с обеих сторон. С помощью двух таких шнуров (по $$$1$$$ минуте каждый) можно отмерить $$$45$$$ секунд – для этого нужно поджечь первый шнур с обеих сторон, а второй только с одной – в момент догорания первого шнура ($$$30$$$ секунд) нужно поджечь второй конец второго: он догорит целиком как раз через $$$45$$$ секунд.
Рассмотрим более общую задачу: пусть у нас есть $$$ n $$$ бикфордовых шнуров с длительностями горения $$$ d_1, d_2, \dots, d_n $$$. Можно ли с помощью них отмерить интервал времени $$$ Time $$$, если поджигать эти шнуры разрешается либо в начальный момент времени, либо в момент догорания какого-либо другого шнура?
Напишите программу, которая решит описанную задачу, или сообщит, что решения не существует. В случае существования нескольких решений, правильным считается любое.
Первая строка содержит единственное целое число – количество бикфордовых шнуров $$$ n $$$ $$$( 1 \leq n \leq 6 )$$$.
Во второй строке записаны $$$ n $$$ целых чисел $$$ d_1, d_2, \dots, d_n $$$ $$$( 1 \leq d_i \leq 120) $$$, разделенных пробелом – длительности горения этих шнуров в секундах.
В третьей строке записано целое число $$$Time$$$ $$$( 1 \leq Time \leq 600 )$$$ – интервал в секундах, который нужно измерить.
Первая строка содержит количество задействованных шнуров $$$ k $$$ $$$( 1 \leq k \leq n )$$$, либо $$$ -1 $$$, если решения не существует.
В случае существования решения, далее следуют $$$ k $$$ строк, каждая из которых содержит одно дробное и три целых числа, разделенных пробелом: $$$ t_{off}$$$ $$$ num $$$ $$$ t_1 $$$ $$$ t_2 $$$. Каждая такая четверка описывает момент догорания шнура $$$ t_{off} $$$ (с точностью до $$$ 10^{-10} $$$ сек); номер самого шнура $$$ num $$$, концы которого были зажжены в моменты времени c индексами $$$ t_1 $$$ и $$$ t_2 $$$. Строки должны быть упорядочены по возрастанию $$$ t_{off} $$$.
Шнуры нумеруются числами $$$ 1, 2, \dots, n $$$ в порядке их появления в исходных данных.
Моменты времени нумеруются числами $$$ 1, \dots, k $$$ в порядке их появления в выводе. Индексом $$$ 0 $$$ обозначается начальный момент времени, а индекс $$$ -1 $$$ используется вместо $$$ t_2 $$$, если второй конец шнура не поджигается.
Если решений несколько, выведите любое из них.
2 60 60 45
2 30 1 0 0 45 2 0 1
1 10 4
-1
| Название |
|---|


