ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1918. Titan Ruins: Artful Manipulations

I do not understand this Test please explain to me
Posted by Axmadjon 6 Jun 2014 10:30
Re: I do not understand this Test please explain to me
Posted by Felix_Mate 29 Jan 2018 00:28
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