H. Тестирование
Задачу добавил: alef
Успешно сдано решений: 27
Важным элементом онлайн-курса является итоговый тест. А при разработке самого итогового теста важно правильно сформировать оценку. Поэтому министерство науки выпустило рекомендации по разработке итогового теста.
Министерство рекомендует включать в итоговый тест $$$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$$$.