Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача Z. Конфеты

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени: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, хотя он и не является минимальным.

Система оценивания

Подзадача 1 (20 баллов)

1N300

В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 2 (20 баллов)

1N5000

В этой подзадаче 10 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (30 баллов)

1N100000

В этой подзадаче 15 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (30 баллов)

1N109

В этой подзадаче 15 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать три целых неотрицательных числа — длину, ширину и высоту ящика, который должен выбрать Петя и в который поместится максимальное количество коробок конфет. Если подходящих ответов несколько, необходимо вывести любой.

Ограничения

1N,a,b,c109

Примеры тестов

Входной файл (sweets.in) Выходной файл (sweets.out)
1
10 1 2 3
3 4 3
2
14 8 3 2
8 3 2

0.044s 0.008s 13