7615. Распределение в Патагонии

В стране Патагонии живет сто благородных семей, и каждый год некоторые из них получают несколько ритуальных кубов от Всевидящего Ока. Он имеет несколько правил распределения кубов: если семья получает хотя бы один куб, то каждый простой делитель их количества должен быть либо 2 либо 3, к тому же, если одна семья получит a > 0 кубов а другая семья в том же году получит b > 0 кубов, то a не должно быть кратно b и наоборот.

Вы – Всевидящее Око. Вам известно, сколько кубов будет доступно для распределения в следующие t лет. Вы ходите найти корректное распределение кубов в каждом году. Каждый год Вы должны распределить все доступные кубы на этот год.

Вход. Первая строка содержит количество годов t (1 ≤ t ≤ 1000). Каждая из следующих t строк содержит количество кубов n_i (1 ≤ n_i ≤ 10¹⁸), которое следует распределить в i-ом году.

Выход. Для каждого года i выведите две строки. В первой строке вывести количество семей m_i (1 ≤ m_i ≤ 100), которое получит хотя бы один куб в i-ый год. Во второй строке вывести m_i чисел – количество кубов, которое получила каждая семья. Сумма этих чисел должна равняться n_i.

Пример входа	Пример выхода
4 1 2 3 10	1 1 1 2 1 3 2 4 6

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Для каждого теста следует представить число n в виде суммы слагаемых вида 2^a3^b, где никакое из слагаемых не делится на другое.

Для n = 1 ответом будет 1, для n = 2 ответом будет 2, для n = 3 ответом будет 3.

Пусть n четное. Найдем представление числа n / 2 в виде требуемой суммы, после чего каждое слагаемое умножим на 2.

Пусть n нечетное. Найдем максимальное k, для которого 3^k ≤ n. Далее разложим в требуемый вид число n – 3^k.

Пример

Пусть n = 10. Тогда 10 = 5 * 2 = (2 + 3) * 2 = 4 + 6.

Пусть n = 90. Тогда 90 = 45 * 2 = (18 + 27) * 2 = (9 * 2 + 27) * 2 = 9 * 4 + 27 * 2 = 36 + 54.

Реализация алгоритма

Функция go(n) возвращает искомое разложение числа n в виде массива слагаемых.

vector<long long> go(long long n)

{

vector<long long> temp;

int i;

Разбираем случаи n = 0 и n = 1.

if (n == 0) return temp;

if (n == 1)

{

temp.push_back(1);

return temp;

}

Если n четное, то получаем разложение числа n / 2 в массиве t. Затем умножаем каждое из полученных слагаемых на 2 и возвращаем массив temp.

if (n % 2 == 0)

{

vector<long long> t = go(n / 2);

for(i = 0; i < t.size(); i++)

temp.push_back(t[i] * 2);

return temp;

}

Число n нечетное. Найдем максимальное k, для которого three = 3^k ≤ n.

long long three = 1;

while (three * 3 <= n)

three *= 3;

Далее раскладываем в требуемый вид число n –three.

temp = go(n - three);

В полученный массив слагаемых добавим еще слагаемое three = 3^k.

temp.push_back(three);

return temp;

}

Основная часть программы. Читаем и обрабатываем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%lld",&n);

res = go(n);

Выводим количество слагаемых в разложении.

printf("%d\n",res.size());

Выводим само разложение.

for(i = 0; i < res.size(); i++)

printf("%lld ",res[i]);

printf("\n");

}