Задача №114679. Разбиение на слагаемые
Даны два целых числа \(n\) и \(k\).
Разбиением числа \(n\) на слагаемые является любой набор положительных целых чисел \(a_1, a_2, \ldots, a_m\), для которых верно, что \(a_1 + a_2 + \ldots + a_m = n\).
Требуется найти разбиение \(n\), слагаемые \(a_i\) в котором имеют ровно \(k\) различных значений.
В первой строке задано целое число \(n\) (\(1 \leq n \leq 100\,000\)) — число, которое нужно разбить на слагаемые.
Во второй строке задано целое число \(k\) (\(1 \leq k \leq n\)) — число различных значений среди слагаемых.
Если требуемого разбиения не существует, то в единственной строке выведите \(-1\).
Иначе, в первой строке выведите число \(m\) (\(1 \leq m \leq n\)) — количество слагаемых в разбиении.
В следующей строке выведите \(m\) целых положительных чисел \(a_1\ a_2\ \ldots\ a_m\) (\(1 \leq a_i \leq n\)), сумма которых равна \(n\), и которые содержат ровно \(k\) различных значений.
Если решений несколько, то выведите любое из них.
В первом примере мы разбили число \(14\) на шесть слагаемых, которые принимают три различных значения \(1\), \(3\), \(5\). Заметим, что это разбиение не единственное, например, также подходит разбиение \([1,\ 1,\ 2,\ 2,\ 4,\ 4]\).
Рассмотрим третий тест из условия. Выпишем все упорядоченные разбиения числа \(5\):
- \([1,\ 1,\ 1,\ 1,\ 1], [5]\) принимают одно различное значение.
- \([1,\ 1,\ 1,\ 2], [1,\ 1,\ 3], [1,\ 2,\ 2], [1,\ 4], [2,\ 3]\) принимают по два различных значения.
В данной задаче \(50\) тестов, включая тесты из условия , каждый из них оценивается в \(2\) балла.
Решения, корректно работающие при \(n \leq 5\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(n \leq 20\), наберут не менее \(60\) баллов.
Решения, корректно работающие при \(20 \lt n\), \(k = 1\), наберут не менее \(10\) баллов.
Решения, корректно работающие при \(20 \lt n\), \(k \leq 2\), наберут не менее \(20\) баллов.
14 3
6 3 3 1 5 1 1
10 1
1 10
5 4
-1