Музыкальное шоу (Fixshow)

Поскольку Дим Димыч вновь забыл поздравить бабушку с днем рождения, он решил устроить для нее грандиозное музыкальное шоу. Для этого он нашел плоскую площадку, в определенных координатах которой расставил N новейших электронных синтезаторов звука. По замыслу Дим Димыча, в некоторые (возможно различные) моменты времени, они должны начать издавать звуки (гарантированно различные), и звучание должно быть длительным. Поскольку Дим Димыч хочет, чтобы бабушка услыхала все звуки как можно скорее, он решил найти такую точку на площадке, в которой впервые будут слышны все N звуков одновременно. Решить такую сложную задачу самостоятельно он не смог, а поэтому прибег к вашей помощи.

Напишите программу, которая вычисляет координаты точки и время, в которое звуки от всех синтезаторов будут в ней впервые слышимы, при условии, что звук распространяется только по воздуху со скоростью С, одинаковой для всех синтезаторов и направлений. Остальными задержками (например, конечной скоростью распространения электрических сигналов) можно пренебречь.

Формат ввода-вывода:

Программа fixshow читает с клавиатуры (стандартного устройства ввода) сначала число N (1<=N<=555) – количество синтезаторов, затем N троек чисел – координаты очередного синтезатора на площадке и время начала его звучания и, наконец, число С (0.1<=C<=1000) – скорость распространения звука.

Значения координат не превышают по модулю 10⁶ и не обязательно целые.

Программа fixshow выводит на экран (стандартное устройства вывода) три числа через пробел: координаты точки, в которой впервые будут слышимы все звуки одновременно, и время, когда это произойдет.

Результат засчитывается, если время отличается от правильного не более чем на 10^-3 и в указанное время в указанной точке будут слышны все синтезаторы.

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

Профессор и помогатор (helper)

У фиксиков в скором времени ожидаются престижные соревнования по ремонту сложнейшего оборудования. Как известно, для устранения особо сложных поломок оборудования фиксики используют помогатор, однако им надо уметь пользоваться в совершенстве!

Профессор Гений Евгеньевич изобрел новую экспериментальную модель помогатора и все хотят с нею срочно ознакомиться. Но… у профессора отпуск! Симка начала уговаривать его дать помогатор ученикам и после долгих уговоров профессор согласился, но с некоторыми условиями:

- Гений Евгеньевич отдаст устройство фиксику X и хочет забрать его после отпуска у фиксика Y.

- Каждый день помогатор должен менять своего владельца.

Всего в классе M учеников и отпуск профессора заканчивается через N дней.

Дим Димычу сразу стало интересно, какие могут быть варианты «путешествия» помогатора по ученикам, а Симке – сколько всего существует таких вариантов.

Формат ввода-вывода:      

Программа helper читает с клавиатуры (стандартного устройства ввода) четыре целых числа N, M (1 ≤ N, M ≤ 10⁹),  X, Y (1 ≤ X, Y ≤ M).

Программа helper выводит на экран (стандартное устройства вывода) одно число – количество возможных вариантов «путешествия» помогатора по ученикам, по заданным правилам. Поскольку число может быть очень большим, выведите остаток от деления этого числа на 10⁹ + 7.

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

Примечание. В первом примере существуют такие варианты «путешествия» помогатора по ученикам:

1 2 1 3 2

1 2 3 1 2

1 3 1 3 2

1 3 2 3 2

1 3 2 1 2

Копир (copier)

Фиксики настолько любопытные существа, что неприятности Нолика во время его знакомства с копиром ничему их не научили. Теперь уже целых N фиксиков забрались под крышку устройства и оказались в разных местах стеклянной панели ксерокса. Тайна их существования оказалась на грани раскрытия, ибо Лизонька, как всегда не вовремя, решила сделать копию какого-то объявления о пропаже очередных вещей профессора Гения Евгеньевича. Чтобы никто не заинтересовался существами на полученной копии, надо получить изображение, на котором ровно k фиксиков (точек) расположено по диагонали снизу вверх. Перепуганные фиксики совсем растерялись и недолго было начаться панике, если бы Симка не предложила такой выход

Представим сканируемую поверхность ксерокса координатной плоскостью с началом координат в левом нижнем углу панели. Тогда расположение фиксиков можно задать координатами точек (i, y_i), i ∈ [1..N], 0 ≤ y_i ≤ N ≤ 200000.

По команде fixup#i фиксик с номером i может переместиться на одну клеточку вверх, т.е. из точки с координатами (i, y_i) в точку с координатами (i, y_i+1). Теперь надо добиться, чтобы за минимальное количество команд k фиксиков оказались в точках с координатами (x_i, 1), (x_i+1, 2), ..., (x_i+k−1, k) (см. рисунок) или определить, что это сделать невозможно.

Формат ввода-вывода:

Программа copier сначала читает с клавиатуры (стандартного устройства ввода) два целых числа N и k (1 ≤ k ≤ N ≤ 200000). Затем считывается N целых чисел y₁, y₂, …, y_N − начальные положения фиксиков.

Программа copier выводит на экран (стандартное устройства вывода) одно число − минимальное количество команд, необходимое для получения нужной конфигурации фиксиков, или «−1» (без кавычек), если это сделать невозможно.

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

Фиксики считают (fixcount)

И опять Дим Димыч с Васькой готовятся к олимпиаде по устному счету. Только теперь им необходимо решать примеры не только на сложение, но и на умножение. Пришлось привлечь не только всех фиксиков, а и профессора Гения Евгеньевича для составления примеров. Это было настолько утомительное занятие, что ребятам начали давать одну последовательность чисел, которую надо было сначала сложить, а потом умножить. Оказалось, что в некоторых случаях результат получался совершенно одинаковый! Например, для последовательности чисел 1, 2 и 3 выполняется свойство 1+2+3=1*2*3=6. Чтобы немного отвлечь ребят от рутинной работы, Симка предложила решить обратную задачу: найти число, которое может быть представлено в виде набора натуральных чисел, сумма и произведение которых давало бы одно и то же число. И такое число нашлось быстро – 4, ведь 4=2+2=2*2. Через некоторое время всеобщими усилиями было найдено число, у которого было РОВНО ДВА различных набора натуральных чисел {a₁,a₂,...,a_p} и {b₁,b₂,...b_q} (2 ≤ p, 2 ≤ q) таких, что

x = a₁ + a₂ + ... + a_p = b₁ + b₂ + ... + b_q = a₁ · a₂ · ... · a_p = b₁ · b₂ · ... · b_q

Но профессор Гений Евгеньевич не остановился на достигнутом! Он окончательно усложнил задачу, предложив посчитать количество целых чисел на заданном интервале, для которых выполняется указанное свойство, причем наборы, отличающиеся только порядком входящих элементов, надо считать одинаковыми. Например, 1+2+3 и 2+3+1 – одинаковые наборы.

Формат ввода-вывода: 

Программа fixcount читает с клавиатуры (стандартного устройства ввода) два целых числа N и M (1≤N≤M≤10¹⁸).

Программа fixcount выводит на экран (стандартное устройства вывода) одно число – количество целых чисел x ∈ [N,M], обладающих указанным свойством.

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

Математика – царица наук (fixolymp)

Победа на олимпиаде по устному счету была одержана! Дим Димыч сидел и с удивлением смотрел на первую полученную медаль. В интернете он нашел информацию о том, что ровно через год состоятся очень престижные соревнования в городе Виннице – XXV Всеукраинский Турнир Чемпионов. Надо готовиться. Но как?

И тут на помощь к нему пришел профессор Гений Евгеньевич. Он пообещал регулярно давать Дим Димычу задачи и постоянно контролировать их выполнение. И вот первое задание.

Дано два натуральных числа A и B. Надо найти два натуральных числа X и Y такие, что

НОД(A, B) = НОД(X, Y )

НОК(A, B) = НОК(X, Y )

X <= Y

Y − X → min

Формат ввода-вывода: 

Программа fixolymp читает с клавиатуры (стандартного устройства ввода) два целых числа A и B (1 ≤ A,B ≤ 10⁹).

Программа fixolymp выводит на экран (стандартное устройства вывода) два целых числа, удовлетворяющих условию задачи.

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