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

H. Тестирование

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

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

Тестирование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Важным элементом онлайн-курса является итоговый тест. А при разработке самого итогового теста важно правильно сформировать оценку. Поэтому министерство науки выпустило рекомендации по разработке итогового теста.

Министерство рекомендует включать в итоговый тест $$$n$$$ вопросов и оценивать его суммарно в $$$m$$$ баллов. Что же касается распределения баллов по вопросам, то здесь предполагается следующий подход. Для каждого вопроса проводится числовая оценка его сложности, так что будут получены целые положительные числа $$$q_1, q_2, \ldots, q_n$$$. После этого необходимо распределить баллы так, чтобы для любых $$$i \neq j$$$ выполнялось равенство $$${q_i}/{q_j} = {b_i}/{b_j}$$$, где $$$b_i$$$ — количество баллов, которое можно набрать за вопрос $$$\#i$$$, а $$$b_j$$$ — количество баллов, которое можно набрать за вопрос $$$\#j$$$. При этом $$$b_i$$$ и $$$b_j$$$ также должны быть целыми положительными числами.

Ваша задача — по заданной сложности вопросов получить удовлетворящее описанным выше требованиям распределение баллов по вопросам.

Входные данные

В первой строке содержатся целые числа $$$n$$$ и $$$m$$$ $$$(1 \le n \le 10^5, \, 1 \le m \le 10^{18})$$$ — количество вопросов в тесте и суммарное количество баллов за тест.

Во второй строке содержатся целые положительные числа $$$q_1, q_2, \ldots, q_n$$$ $$$\left(\sum \limits_{j=1}^{n} q_j \le 10^{18} \right)$$$, $$$q_j$$$ — сложность вопроса $$$\#j$$$.

Выходные данные

Выведите $$$n$$$ целых положительных чисел $$$b_1, b_2, \ldots, b_n$$$, где $$$b_i$$$ — количество баллов, которые следует начислять за вопрос $$$\#i$$$.

Напомним, что должны выполняться равенства $$${q_i}/{q_j} = {b_i}/{b_j}$$$ для любых $$$i$$$ и $$$j$$$, а также равенство $$$\sum\limits_{i = 1}^n b_i = m$$$.

Гарантируется, что ответ всегда существует.

Пример

Входные данные
4 45
8 6 12 4
Выходные данные
12 9 18 6 

Примечание

Поясним приведённый пример.

Действительно, сумма баллов $$$b_i$$$ за все ответы будет равна $$$12 + 9 + 18 + 6 = 45$$$, как и требовалось в условии.

Легко проверить, что выполняются все соотношения между элементами:

$$$a_1 / a_2 = 8/6 = 4/3 = 12/9 = b_1/b_2$$$;

$$$a_1 / a_3 = 8/12 = 2/3 = 12/18 = b_1/b_3$$$;

$$$a_1 / a_4 = 8/4 = 2 = 12/6 = b_1/b_4$$$;

$$$a_2 / a_3 = 6/12 = 1/2 = 9/18 = b_2/b_3$$$;

$$$a_2 / a_4 = 6/4 = 3/2 = 9/6 = b_2/b_4$$$;

$$$a_3 / a_4 = 12/4 = 3 = 18/6 = b_3/b_4$$$.

Сдать задачу

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