| Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 1 сек | |
| Входной файл: | sweets.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | sweets.out | |||
| Максимальный балл: | 100 |
Кондитерская фабрика города П, в котором живет Петя, делает очень вкусные конфеты. Как-то раз, Петя собрался в гости к своему другу Васе, который живет в городе М. От города П до города М Петя решил доехать на поезде и взять с собой в подарок как можно больше коробок вкусных конфет.
Каждая коробка конфет имеет размеры a × b × c сантиметров, где a — длина, b — ширина и c — высота коробки. Для перевозки конфет Петя хочет использовать один большой ящик в форме прямоугольного параллелепипеда. В ящик должны быть уложены все коробки конфет. Для того чтобы не повредить их, все коробки в ящике должны сохранять исходную ориентацию и располагаться в одном направлении. Петя может использовать ящик любого размера, но по правилам железнодорожных перевозок размер ящика по сумме трех измерений не может превышать N сантиметров.
Требуется написать программу, которая по заданным числам N, a, b и c определяет размер ящика, который должен использовать Петя, чтобы в него поместилось максимальное количество коробок конфет.
В первом примере выгоднее всего взять ящик размером 3 × 4 × 3 сантиметров, в который поместится три коробки конфет в длину, две коробки конфет в ширину и одна коробка конфет в высоту.
Во втором примере для того, чтобы разместить хотя бы две коробки конфет, нужен ящик размером хотя бы 8 × 3 × 4, у которого сумма измерений равна 15. В подходящий ящик поместится максимум одна коробка конфет. Подходящим также является ящик размером 9 × 3 × 2, хотя он и не является минимальным.
Первая строка входного файла содержит разделенные пробелами четыре целых числа: N, a, b, с.
Выходной файл должен содержать три целых неотрицательных числа — длину, ширину и высоту ящика, который должен выбрать Петя и в который поместится максимальное количество коробок конфет. Если подходящих ответов несколько, необходимо вывести любой.
1 ≤ N, a, b, c ≤ 109
Данная задача содержит четыре подзадачи. Каждый тест в каждой подзадаче оценивается независимо в 2 балла.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|
| N | |||
| 1 | до 20 | 1 ≤ N ≤ 300 | |
| 2 | до 20 | 1 ≤ N ≤ 5000 | |
| 3 | до 30 | 1 ≤ N ≤ 100 000 | |
| 3 | до 30 | 1 ≤ N ≤ 109 |
По запросу сообщаются баллы за каждую подзадачу.
| № | Входной файл (sweets.in) |
Выходной файл (sweets.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|