HINT: you must read problem on english version.
Перевод на русский язык плох. Нифига непонятно, о чём речь в 4 пункте. А вот в английской версии всё зашибись.
Суть в следующем. Есть n рычагов, каждый рычаг можно поставить ровно в одно из n состояний. Изначально есть 1 монета. Пусть на некотором шаге имеется i монет (1<=i<=n). Если ничего не делать, то со временем станет i-1, i-2, ... , 1 монет. Можно применить зарядку (в любой момент). Пусть при применении зарядки i рычаг находится в состоянии j (1<=j<=n). Тогда число монет становится j. Нужно найти все такие состояния рычагов (т.е. вектор (x1,...,xn) : 1<=xi<=n), что с помощью использования некоторых зарядок можно получить n монет.
Примеры:
1)n=2
все возможные комбинации: (1,1) (1,2) (2,1) (2,2)
получить 2 можно 2 способами: (2,1) и (2,2) - в этом случае сразу получаем 2 монеты
почему не подходят (1,1) и (1,2)? в этом случае снова станет 1 монета
2)n=4
комбинации из ответа: (4,*,*,*) -> кол-во=4*4*4
(3,4,1,*) -> кол-во=4
(3,4,2,*) -> кол-во=4
(3,4,3,*) -> кол-во=4
(3,*,4,*) -> кол-во=4*4
(2,3,4,*) -> кол-во=4
(2,4,*,*) -> кол-во=4*4
ответ=112
почему (3,4,2,*) даёт решение? Число монет меняется так:вначале 1 монета. Если не делать зарядку, то 1 монета так и будет. Если применить зарядку, то станет 3 монеты. Далее если не делать зарядку, то станет 2 монеты: потом можно сделать зарядку и получить 4 монеты либо не делать зарядку и получить 1 монету; если сделать зарядку, то получим 2 монеты: потом если не делать зарядку,то получим 1 монету, а если сделать зарядку, то получим 4 монеты.
Edited by author 29.01.2018 00:31
