10^(n-2)+2^(n-2)

I think for 4 = 104

I think for 4 = 112

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