|
Геометрическая игра на планшете
(Время: 1 сек. Память: 32 Мб Сложность: 57%)
Маленький Андрей изучает геометрические фигуры при помощи игры на планшете. У него есть равнобедренные прямоугольные треугольники четырёх цветов и ориентаций: жёлтые, зелёные, красные и синие. Для каждой разновидности треугольников есть заданное количество экземпляров этих треугольников. Более точно: у Андрея есть A жёлтых, B зелёных, C красных и D синих треугольников. Известно, что A ≥ B ≥ C ≥ D. Все треугольники одинаковые по размеру, но у каждого есть своя ориентация, которую нельзя менять. Треугольники одного цвета имеют одну и ту же ориентацию.
Помимо этого, у мальчика есть N пустых ячеек, стороны которых совпадают с катетами треугольников. Игра происходит пошагово: на каждом шаге Андрей может взять очередной треугольник и переместить его параллельным сдвигом в одну из ячеек. При этом в одну ячейку можно поместить либо вместе жёлтый и красный треугольники, либо вместе зелёный и синий, либо один любой треугольник из имеющихся.
На каждом шаге можно переместить треугольник строго одного текущего цвета. Сначала это жёлтый, на следующем ходе зелёный, далее красный и затем синий. Далее снова жёлтый, зелёный, красный, синий и т.д по циклу. Если места для текущего цвета нет либо треугольники текущего цвета закончились, то этот цвет пропускается и ходит следующий по порядку цвет.
Допустим, в данном шаге есть треугольник текущего цвета. Если ещё есть пустая ячейка, данный треугольник обязательно помещается в эту ячейку. Если пустые ячейки закончились, но есть полупустая ячейка с парным текущему цветом, то треугольник помещается в неё. Игра длится до тех пор, пока есть цвет, который можно поместить в какую‑то ячейку.
Определите: сколько каких треугольников Андрей распределит в конечном итоге по ячейкам.
Входные данные
Входной файл INPUT.TXT содержит числа A, B, C, D, каждое в своей строке. Гарантируется, что A ≥ B ≥ C ≥ D. В пятой строке содержится число N – количество пустых ячеек. 1 ≤ A, B, C, D, N ≤ 1018.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ в четыре строки: для каждого соответствующего цвета укажите: сколько треугольников этого цвета получится поместить в ячейки. В первую строку выведите число жёлтых треугольников, во вторую – зелёных, в третью – красных и в четвёртую – синих.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 20 5 3 2 14 | 8 5 3 2 |
2 | 7 7 7 7 9 | 5 4 5 4 |
Система оценки
Решения, верно работающие при 1 ≤ A, B, C, D, N ≤ 1000, будут оцениваться в 30 баллов.
Решения, верно работающие при 4 ≤ A+B+C+D ≤ 106 и 1 ≤ N ≤ 106, будут оцениваться в 60 баллов.
Пояснение
Для первого примера из условия проиллюстрируем некоторые промежуточные ситуации:
 N=14
Положение после 14 первых ходов, если Андрей раскладывал треугольники по ячейкам слева направо. На данный момент закончились все пустые ячейки и треугольники красного и синего цветов:
Итоговое положение после 18 ходов. Дополнительно получилось разложить ещё три жёлтых треугольника и один зелёный. Зелёные треугольники тоже закончились, а для жёлтых закончились места. Итого Андрей разложил 8 жёлтых, 5 зелёных, 3 красных и 2 синих треугольника:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |