Условие (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 | Решений нет |
Теперь, зная алгоритм, можно написать программу, выполняющую необходимые действия.
Код данной программы :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> using namespace std; int main() { int n; cin >> n; if (n < 4 || n == 6) // особые случаи (1) cout << "Решений нет" << endl; else if (n == 4) // особые случаи (2) { cout << "1 2 1 0" << endl; cout << "2 0 2 0" << endl; } else if (n == 5) // особый случай (3) cout << "2 1 2 0 0" << endl; else // алгоритм для общего случая { int number[n]; // создаем массив членов последовательности for (int i = 0; i < n; i++) // приравниваем все числа к нулю number[i] = 0; number[0] = n - 4; // выставляем значения для ненулевых членов number[1] = 2; number[2] = 1; number[n - 4] = 1; for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран cout << number[i] << " "; cout << endl; } return 0; } |
Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:
Хорошо. Но остались вопросы.
— Будет ли найденное решение единственным?
— Если нет, то для каких последовательностей существуют несколько решений и как их найти все?
Спасибо, ответил (уточнил примечание). Других решений у этой задачи нет.
Понял.
Только 1 2 1 0. Значит 2 0 2 0 просто галлюцинация….
Извиняюсь, частные решения искал давно, перепроверял только общее. Исправил случай n = 4.
Это наводит на мысль, что не хватает доказательства единственности решения для достаточно длинных последовательностей.
Так и просится доказательство от противного. Начинаем словами «предположим, что существует ещё одно решение» и заканчиваем «получили противоречие».