Ограничение памяти 16 мегабайт

 

Менеджер упаковочной фабрики, которая специализируется на упаковке хрупких предметов, заказал ящики, размеры которых равны числам Фибоначчи. Мотивы такого решения не известны, впрочем, для нашей задачи это не так уж важно. Предмет, размер которого в точности равен какому-нибудь числу Фибоначчи, можно упаковать в один из ящиков. Но если размер предмета другой, то для его упаковки требуется уплотнительный материал, чтобы заполнить ящик и предотвратить поломку предмета при транспортировке. Необходимое количество упаковочного материала в точности равно разности размера ящика и размера предмета. Предметы нельзя разбирать на части и каждый предмет должен быть упакован в отдельный ящик. Другая проблема состоит в том, что фабрика получает ежедневно только F единиц упаковочного материала, и в конце рабочего дня весь оставшийся материал выбрасывается. Ваша задача – максимизировать количество упакованных за день предметов.

Числа Фибоначчи определяются так: F(n) = n, если n < 2 и F(n) = F(n-1) + F(n-2) если n > 1. Вот несколько первых чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Вход

В первой строке входного файла записаны три целых числа: количество предметов W (0 < W < 1000), количество имеющегося уплотнительного материала F (1 < F < 1000) и максимальный размер предмета S (1 < S < 10⁸). Вторая строка содержит W целых чисел – размеры предметов.

Выход

Запишите в выходной файл максимальное количество предметов, которые можно упаковать за день.

Примеры входа и выхода

packing.in	packing.out
4 10 30 7 15 30 5
11 100 5812167 20 40 30 15 17 5812167 23 43 33 13 37

 

Задача 5. «Коррозия металла»

Входной файл: Input.txt

Выходной файл: Output.txt

Ограничение времени: 1 секунда

Ограничение памяти: 64 М байт

 

Для хранения двух агрессивных жидкостей А и В используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1,..., N) известно время его растворения жидкостью А - a_i и жидкостью В - b_i. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа. Требуется спроектировать такую перегородку, время растворения которой было бы максимальным.

 

Вход

В первой строке входного файла содержится целое число N (1 ≤ N ≤ 1000) - количество листов. Далее идут N пар чисел a_i, b_i, i = 1,..., N. a_i и b_i - неотрицательные целые числа, не превосходящие 1,000,000. Все числа разделяются пробелами и/или символами перевода строки.

Выход

Первая строка выходного файла должна содержать максимальное время растворения с точностью до трех дробных цифр. Во второй строке нужно вывести последовательность листов в порядке слева направо (слева находится жидкость A, справа - жидкость B), для которой достигается максимальное время. Числа разделять одним пробелом.