Задача A. Подарок ≡

Условие

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

Поликарп очень аккуратен. Он упаковывает подарок в коробку, имеющую форму прямоугольного параллелепипеда, и оклеивает всю ее поверхность клетчатой бумагой. При этом каждая грань коробки представляет собой прямоугольник, состоящий из целых клеток. На рисунке изображен пример такой упаковки подарка.

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

У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из n клеток. Каким будет максимальный объем коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нем. Поликарп может использовать для оклеивания коробки не все клетки.

Напишите программу, которая по заданному количеству клеток n находит размеры коробки максимального возможного объема.

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

Входной файл содержит одно целое число n (6 ≤ n ≤ 10¹³) — количество клеток на листе клетчатой бумаги.

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

Выведите в первую строку выходного файла максимальный объем коробки, которую может подарить Поликарп. Объем следует выводить в «кубических клетках», то есть единицей измерения является куб со стороной равной длине стороны клетки.

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

Решения, корректно работающие при n ≤ 5000, будут оцениваться из 30 баллов, а решения, корректно работающие при n ≤ 10⁸, будут оцениваться из 70 баллов.

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

6

1
1 1 1

37

12
3 2 2

Задача B. ЮграНефтеТранс ≡

Условие

Ханты-Мансийский автономный округ — Югра является важнейшим нефтяным регионом России. Добыча нефти составляет 267 млн. т. в год, её транспортировка осуществляется по трубопроводам, общая длина которых превышает длину экватора Земли.

Система транспортировки нефти представляет собой совокупность n распределительных станций и m трубопроводов. Каждый трубопровод соединяет две различные станции. Между любыми двумя станциями проложено не более одного трубопровода.

Эффективность работы станций существенно зависит от вязкости нефти. Поэтому компания "ЮграНефтеТранс", в ведении которой находится сеть трубопроводов, заказала инновационному исследовательскому предприятию разработку и изготовление новых сверхточных датчиков вязкости на основе самых современных технологий.

Изготовление датчиков — процесс трудоёмкий и дорогостоящий, поэтому было решено изготовить k датчиков (k ≤ 40) и выбрать k различных станций, на которых датчики будут установлены. Необходимо осуществить выбор станций так, чтобы датчики контролировали все трубопроводы: для каждого трубопровода хотя бы один датчик должен быть установлен на станции, где начинается или заканчивается этот трубопровод.

Напишите программу, которая проверяет, существует ли требуемое расположение датчиков, и в случае положительного ответа находит это расположение.

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

В первой строке входного файла записаны три натуральных числа — n, m и k (k ≤ n ≤ 2000, 1 ≤ m ≤ 10⁵, 1 ≤ k ≤ 40). Далее следуют m строк, каждая из которых описывает один трубопровод. Трубопровод задаётся двумя целыми числами — порядковыми номерами станций, которые он соединяет. Станции пронумерованы от 1 до n. Гарантируется, что к любой станции подведён хотя бы один трубопровод и между любыми двумя станциями проложено не более одного трубопровода. Числа в каждой строке разделены пробелами.

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

В первую строку выходного файла выведите слово "Yes", если требуемое расположение датчиков существует, в противном случае — слово "No". В случае положительного ответа выведите во вторую строку выходного файла k различных целых чисел — номера станций, на которых необходимо установить датчики. Номера можно выводить в любом порядке. Если существует несколько подходящих расположений датчиков, выведите любое из них. Разделяйте числа во второй строке пробелами.

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

2 1 2
1 2

Yes
1 2

3 3 1
1 2
2 3
3 1

No

7 6 2
1 2
1 3
1 4
2 5
2 6
2 7

Yes
1 2

5 5 2
1 2
1 3
1 4
1 5
4 5

Yes
4 1

Задача C. А олени — лучше! ≡

Условие

Вы уже знаете, сколько нефти добывается в Ханты-Мансийском автономном округе. Другой хозяйственной отраслью Югры является оленеводство. Нередко можно увидеть, как на нефтяной площадке, окружённой изгородью, работают нефтяники, а вокруг изгороди пасутся олени.

Оленевод Ванхо привязал своего оленя Ахтамака к изгороди нефтяной площадки, имеющей форму выпуклого многоугольника. Олень был привязан на длинной верёвке, чтобы он не убежал и при этом мог пастись. Вокруг нефтяной вышки растёт такой вкусный ягель, что олень тут же принялся его щипать.

Напишите программу, вычисляющую площадь участка вне изгороди, ягель на которой будет доступен оленю. Форма изгороди, точка привязывания и длина верёвки задаются во входном файле.

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

В первой строке входного файла записано целое число n — количество углов изгороди (3 ≤ n ≤ 100). В последующих n строках записаны координаты углов изгороди в порядке обхода по часовой стрелке. В последней строке записаны три числа — координаты точки привязывания оленя к изгороди и длина верёвки. Все координаты целые и не превосходят по модулю 10⁴. Длина верёвки — целое положительное число, не превосходящее 10⁴. Числа в каждой строке разделены пробелами. Гарантируется, что изгородь представляет собой строго выпуклый многоугольник и точка привязывания оленя лежит на его границе.

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

В выходной файл выведите значение площади с точностью не менее 10⁻³.

Решения, корректно работающие на тестах из примеров, а также в случае, если длина верёвки не превосходит половины периметра изгороди и изгородь представляет собой прямоугольник со сторонами, параллельными осям координат, будут оцениваться из 30 баллов. Решения, корректно работающие на тестах из примеров, а также в случае, если длина верёвки не превосходит половины периметра изгороди, будут оцениваться из 60 баллов.

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

4
0 0
0 2
4 2
4 0
1 2 2

7.06858

3
0 0
0 1
1 0
0 0 2

11.49557428756