Масив і знову додавання#228

Масив і знову додавання

1 секунда

256 мегабайтів

Складна

Є масив $a$ , елементи якого пронумеровані від $1$ до $100$ . Початково $a_{i} = 0$ a_i = 0 для $1 \leq i < 100$ 1 \leq i < 100, а останній елемент $a_{100}$ a_{100} рівний $1$ .

Масив $a$ можна змінювати, використовуючи операції збільшення. Для того, щоб виконати $m$ операцій збільшення, необхідно вибрати $m$ цілих чисел $p_{1}, p_{2}, \dots, p_{m}$ p_1, p_2, \dots, p_m ( $1 \leq p_{i} < 100$ 1\le p_i < 100) та послідовно виконати операції присвоєння $a_{p_{i}} \leftarrow (a_{p_{i}} + a_{p_{i} + 1})$ a_{p_i} \leftarrow (a_{p_i} + a_{p_i + 1}) для $i$ від $1$ до $m$ .

Задано ціле число $n$ . Знайдіть послідовність операцій збільшення, після виконання яких елемент на першій позиції в масиві $a$ стане рівним $n$ .

Вхідні дані

У першому рядку задано два цілі числа $t$ , $g$ ( $1 \leq t \leq 100$ 1 \le t \le 100, $0 \leq g \leq 5$ 0 \leq g \leq 5) — кількість наборів вхідних даних та номер блоку тестів відповідно.

У наступних $t$ рядках задано по одному цілому числу $n$ ( $1 \leq n \leq 1 0^{18}$ 1 \le n \le 10^{18}) — значенню, якому повинно дорівнювати $a_{1}$ a_1 після виконання операцій збільшення в черговому наборі.

Вихідні дані

Для кожного набору вхідних даних у першому рядку виведіть одне ціле число $m$ ( $0 \leq m \leq 2000$ 0 \leq m \leq 2000) — кількість операцій збільшення.

У другому рядку виведіть $m$ цілих чисел $p_{i}$ p_i ( $1 \leq p_{i} < 100$ 1 \le p_i < 100) — параметри операцій збільшення.

Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.

Приклади

Приклад

1 0
1

99
99 98 ... 7 6 5 4 3 2 1

Приклад

2 0
3
16

101
99 98 ... 7 6 5 4 3 2 1 1 1
103
99 98 ... 7 6 5 4 4 3 3 2 2 1 1

Примітка

Для наочності приклади вихідних даних в умові зменшено: для отримання правильної відповіді необхідно замінити «...» на послідовність цілих чисел від $97$ до $8$ .

Розглянемо другий набір вхідних даних другого прикладу $n = 16$ n = 16. Перші 8 елементів масиву $a$ після виконання чергової операції виглядають наступним чином:

$p_{1}$ p_1 = 99, $a = [0, 0, 0, 0, 0, 0, 0, 0, \dots, 0, 0, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 0, 1, 1];
$p_{2}$ p_2 = 98, $a = [0, 0, 0, 0, 0, 0, 0, 0, \dots, 0, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 1, 1, 1];
$\dots$
$p_{93} = 7$ p_{93} = 7, $a = [0, 0, 0, 0, 0, 0, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 1, 1, \ldots, 1, 1, 1, 1];
$p_{94} = 6$ p_{94} = 6, $a = [0, 0, 0, 0, 0, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{95} = 5$ p_{95} = 5, $a = [0, 0, 0, 0, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{96} = 4$ p_{96} = 4, $a = [0, 0, 0, 1, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 1, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{97} = 4$ p_{97} = 4, $a = [0, 0, 0, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{98} = 3$ p_{98} = 3, $a = [0, 0, 2, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 2, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{99} = 3$ p_{99} = 3, $a = [0, 0, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{100} = 2$ p_{100} = 2, $a = [0, 4, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 4, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{101} = 2$ p_{101} = 2, $a = [0, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{102} = 1$ p_{102} = 1, $a = [8, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [8, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{103} = 1$ p_{103} = 1, $a = [16, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [16, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1].

Оцінювання

У перших чотирьох блоках тестів дозволяється використати не більше ніж 300 операцій збільшення.

( $4$ бали): $n \leq 100$ n \leq 100;
( $6$ балів): $n = k^{2}$ n = k^2 для деякого цілого $1 \leq k \leq 100$ 1 \le k \le 100;
( $10$ балів): $n = (2^{k} - 1)$ n = (2^k - 1) для деякого цілого $k$ ;
( $13$ балів): $n$ — число Фібоначчі ( $n$ є одним з елементів послідовності, де кожен елемент є сумою двох попередніх: $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$ 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots);
(до $67$ балів): без додаткових обмежень. Нехай максимальна кількість використаних операцій збільшення дорівнює $c$ . Якщо $c \leq 300$ c \le 300, то ви отримаєте $67$ балів, а інакше ви отримаєте ( $17 + ⌊ \frac{2000 - c}{34} ⌋$ 17 + \left \lfloor \frac{2000 - c}{34} \right \rfloor) балів.

Код на мові C++, який обчислює кількість балів за останній блок тестів залежно від кількості використаних операцій збільшення:

((c <= 300) ? 67 : (17 + (2000 - c) / 34))