Интересная последовательность

Условие (OCPC-2015)

Дана последовательность из [latex]n[/latex] чисел: [latex]x_0[/latex], [latex]x_1[/latex], [latex]x_2, \ldots, x_{n-1}[/latex], где [latex]x_0[/latex] — кол-во чисел [latex]0[/latex] в данной последовательности, [latex]x_1[/latex] — кол-во чисел [latex]1[/latex], и так далее…

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

Число [latex]n[/latex] — количество членов последовательности.

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

Искомая последовательность.

Размышления над решением:

Обратим внимание, что сумма всех чисел данной последовательности является кол-вом используемых в ней чисел, что равно кол-ву членов последовательности. Иными словами, должно выполняться равенство:

[latex]x_0 + x_1 + [/latex]…[latex] + x_{n-1} = n[/latex] (1)

Далее заметим, что [latex]x_0[/latex] не может равняться нулю (ведь записав туда [latex]0[/latex], мы сразу же увеличиваем кол-во нулей до одного). Тогда [latex]x_0[/latex] равняется другому числу [latex]k[/latex], положим, большему чем 2. Тогда, [latex]x_k = 1[/latex].

Далее, положив [latex]x_1 = 2[/latex] и [latex]x_2 = 1[/latex], получаем последовательность, не нуждающуюся в дальнейших преобразованиях, в чем легко убедиться. Для наглядности:

Член последовательности [latex]x_0[/latex] [latex]x_1[/latex] [latex]x_2[/latex] [latex]x_k[/latex]
Чему равен k 2 1 0 1 0
Комментарий [latex]k[/latex] будет найдено ниже Количество чисел [latex]1[/latex] равно двум Количество чисел [latex]2[/latex] равно одному На этом промежутке только нули [latex]k[/latex] больше двух На этом промежутке только нули

Теперь вычислим [latex]k[/latex]. По формуле (1):

[latex]k + 2 + 1 + 1 = n[/latex];  [latex]k = n — 4[/latex]

(Примечание: При попытки подставить другие значения вместо  [latex]x_1[/latex] или  [latex]x_2[/latex] получится нестабильная последовательность, членам которой не получится присвоить значения согласно условию. Положив, например,  [latex]x_1 = 3[/latex], нам придется увеличить кол-во единиц, что приведет к необходимости использовать другие числа последовательности, что в итоге обязательно приведет к нарушению необходимого условия (1) — сумма уже присвоенных ненулевых чисел попросту превысит количество ее оставшихся членов. Аналогично, если присвоить [latex]x_2 = 2[/latex], и уж тем более, при внесении более «крупных» изменений в последовательность. Таким образом, найденное решение является единственным.)

Очевидно, минимальное «рабочее» значение  [latex]n[/latex] равно семи (при  [latex]k = 2 + 1 = 3[/latex]).

Тесты (1) :

 [latex]n[/latex]  [latex]x_0[/latex]  [latex]x_1[/latex]  [latex]x_2[/latex]  [latex]x_3[/latex]  [latex]x_4[/latex]  [latex]x_5[/latex]  [latex]x_6[/latex]  [latex]x_7[/latex]  [latex]x_8[/latex]  …
 7 3 2 1 1 0 0 0
8 4 2 1 0 1 0 0 0
9 5 2 1 0 0 1 0 0 0
[latex]n — 4[/latex] 2 1 0

Для [latex]n[/latex] меньше семи, решение (или их отсутствие) было найдено подбором.

Тесты (2) :

[latex]n[/latex] [latex]x_0[/latex] [latex]x_1[/latex] [latex]x_2[/latex] [latex]x_3[/latex] [latex]x_4[/latex] [latex]x_5[/latex]
1 Решений нет
2 Решений нет
3 Решений нет
4 1

2

2

0

1

2

0

0

5 2 1 2 0 0
6 Решений нет

Теперь, зная алгоритм, можно написать программу, выполняющую необходимые действия.

Код данной программы :

Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:

Ideaone.com

5 thoughts on “Интересная последовательность

  1. Это наводит на мысль, что не хватает доказательства единственности решения для достаточно длинных последовательностей.
    Так и просится доказательство от противного. Начинаем словами «предположим, что существует ещё одно решение» и заканчиваем «получили противоречие».