Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

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

Автор задачи: Всероссийская олимпиада школьников по информатике

Первоисточник: Пробный тур регионального этапа 2017

Задачу добавил: alef

Успешно сдано решений: 15

Ограничение по времени:

2 секунды

Ограничение по памяти:

512 мегабайт

Кондитерская фабрика города П, в котором живет Петя делает очень вкусные конфеты. Как-то раз Петя собрался в гости к своему другу Васе, который живет в городе М. От города П до города М Петя решил доехать на поезде и взять с собой в подарок как можно больше коробок вкусных конфет.

Каждая коробка конфет имеет размер a × b × c сантиметров, где a – длина, b – ширина и c – высота коробки. Для перевозки конфет Петя хочет использовать один большой ящик в форме прямоугольного параллелепипеда. В ящик должны быть уложены все коробки конфет. Для того чтобы не повредить их, все коробки в ящике должны сохранять исходную ориентацию и располагаться в одном направлении. Петя может использовать ящик любого размера, но по правилам железнодорожных перевозок размер ящика по сумме трех измерений не может превышать N сантиметров.

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

Формат входных данных

Первая строка входных данных содержит разделенные пробелами четыре целых числа: N, a, b, с (1  N, a, b, c  109).

Формат выходных данных

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

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

входные данные

выходные данные

10 1 2 3

3 4 3

14 8 3 2

9 3 2

Пояснения к примерам

В первом примере выгоднее всего взять ящик размером 3 × 4 × 3 сантиметров, в который поместится три коробки конфет в длину, две коробки конфет в ширину и одна коробка конфет в высоту.

Во втором примере для того, чтобы разместить хотя бы две коробки, нужен ящик размером хотя бы 8 × 3 × 4, у которого сумма измерений равна 15. Поэтому в подходящий ящик поместится максимум одна коробка конфет. В том числе для этого подходит ящик размером 9 × 3 × 2, хотя он и не является минимальным.

Описание подзадач и системы оценивания

Данная задача содержит четыре подзадачи. Каждый тест в каждой подзадаче оценивается независимо в 2 балла.

Подзадача

Баллы

Дополнительные ограничения

Необходимые подзадачи

Информация о проверке

N

1

до 20

1 ≤ N ≤ 300


баллы

2

до 20

1 ≤ N 5000


баллы

3

до 30

1 ≤ N ≤ 100 000


баллы

4

до 30

1 ≤ N 109


баллы

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

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



Сдать задачу

Задать вопрос жюри по этой задаче