2011, Область

1. «Поедание сыра» (20 баллов)

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

Всего на заводе живет m мышей. Для i-й мыши известна ее скорость поедания сыра s_i, мышь может съесть s_i грамм сыра в час.

Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить n головок сыра. Про каждую головку известны: r_i — к началу какого часа она будет изготовлена, d_i — в начале какого часа она начнет портиться и p_i — вес головки сыра в граммах.

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

Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина t, такая что какую-либо головку все еще продолжают есть через t часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.

Ограничения: .

Ввод: из файла cheese.in. В первой строке находятся целые числа n и m. Следующие n строк содержат по три целых числа: p_i, r_i, d_i. Далее следуют m строк, каждая из которых содержит по одному целому числу s_j.

Вывод: в файл cheese.out. Выводится одно вещественное число — искомое минимальное t. Ответ должен отличаться от правильного не более, чем на 10^—4.

Пример:

Ввод 1 Ввод 2

2 2 1 1

13 0 4 1 0 2

10 1 3 1

4

2

Вывод 1 Вывод 2

0.5 0.0

В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2,5 часа первая мышь доедает вторую головку сыра (на 0,5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0,5 часа позже чем она начала портиться.

Во втором примере мышь успевает съесть сыр до того как он начинает портиться.

2. «Разбиение на слагаемые» (5 баллов)

Разбиения числа n на слагаемые — это набор целых положительных чисел, сумма которых равна n. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.

Например, существует 7 разбиений числа 5 на слагаемые:

5 = 1+1+1+1+1

5 = 1+1+1+2

5 = 1+1+3

5 = 1+2+2

5 = 1+4

5 = 2+3

5 = 5

В приведенном примере разбиения упорядочены лексикографически — сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.

Ограничения: .

Ввод из файла next.in. Разбиение числа n на слагаемые. Слагаемые в разбиении следуют в неубывающем порядке.

Вывод в файл next.out. Выводится одна строка — разбиение числа n на слагаемые, следующее в лексикографическом порядке после приведенного во входном файле. Если во входном файле приведено последнее разбиение числа n на слагаемые, выведите No solution.

Пример

Ввод 1 Ввод 2

5=1+1+3 5=5

Вывод 1 Вывод 2

5=1+2+2 No solution