Манкала - это название семейства настольных игр, которые обычно включают в себя серию чашек, наполненных бусинками, которыми манипулируют игроки. Эта задача будет использовать определенный набор правил для варианта игры пасьянса.

Доска состоит из «корзины» на одном конце, за которой следует бесконечное количество чашек, пронумерованных, начиная с 1. В некоторых чашках будет определенное количество шариков. Если в nчашке точно есть nбусинки, вы можете «сеять» бусинки из нее. Посев означает вынуть все nшарики из чашки, а затем положить их по одному в каждую чашку по направлению к корзине. Последняя бусинка уйдет в корзину. Игрок выигрывает, когда все бусины на доске находятся в корзине.

Ясно, что есть много досок, которые нельзя выиграть, например, если во второй чашке ровно один шарик. Нет законных игр, потому что все чашки с 0 бусами не могут быть посеяны, а вторая чашка не имеет достаточного количества бусин для посева. Это явно не весело, поэтому ваша задача будет создавать выигрышные доски.

задача

При наличии положительного целого числа, представляющего количество шариков, выведите список неотрицательных целых чисел, представляющих количество шариков, которое следует поместить в каждую чашку, чтобы сделать доску с выигрышными сторонами, как описано выше. Этот список не должен содержать никаких завершающих нулей.

Для любого заданного количества бусинок всегда существует ровно одна конфигурация выигрышной доски.

демонстрация

Это демонстрация того, как разыграть выигрышную доску и ввести 4. Выигрышная доска есть [0, 1, 3]. Мы начинаем с единственного доступного хода, высевая бусы из третьей чашки, чтобы получить [1, 2, 0]. Теперь у нас на самом деле есть выбор, но единственно правильная сеют первую чашку, получая: [0, 2, 0]. Затем мы сеем вторую чашку [1, 0, 0]и, наконец, снова сеем первую чашку, чтобы получить все пустые чашки.

Тестовые случаи:

1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]

Большое спасибо PeterTaylor за создание программы для генерации тестовых случаев!

CJam (21 байт)

M{_0+0#_Wa*\)+.+}ri*`

Онлайн демо

объяснение

Я независимо вывел технику «игры», упомянутую в этой статье . По индукции мы докажем, что для данного количества бусин существует ровно одна выигрышная доска.

Базовый случай: с 0 бусинками, единственная выигрышная доска - пустая.

Индуктивный шаг: если мы сеем из чашки, kто на следующем ходу чашка kбудет пустой, и каждая чашка ближе к корзине будет содержать по крайней мере один шарик. Поэтому мы можем найти уникальную выигрышную доску с nбусами из выигрышной доски с n-1бусинами, найдя пустую чашку с наименьшим номером, взяв одну бусину из корзины и одну из каждой чашки под этой пустой чашкой и поместив их все в пустую чашку.

рассечение

M           e# Start with an empty board
{           e# Loop
  _0+0#     e#   Find position of first 0 (appending to ensure that there is one)
  _Wa*      e#   Make array of that many [-1]s
  \)+       e#   Append the index plus 1 (since board is 1-indexed)
  .+        e#   Pointwise addition
}
ri*         e# Read integer from stdin and execute loop that many times
`           e# Format for display

Python, 42 41 байт

m=lambda n,i=2:n*[1]and[n%i]+m(n-n%i,i+1)

JavaScript (ES6), 63 37 байт

f=(n,d=2)=>n?[n%d,...f(n-n%d,d+1)]:[]

Порт ответа @ orlp на Python. Пояснение: Рассмотрим общее количество бусинок в iй и выше чашках. Каждая игра из одной из этих чашек удалит iбусы из этой суммы. (Например, если i3, и вы играете с пятого кубка, вы уменьшаете количество бус в этом кубке на пять, но вы также добавляете один к четвертому и третьему кубкам.) Таким образом, общее количество должно быть кратным из i. Теперь эта i-1чашка не может содержать iили больше шариков, поэтому для того, чтобы она оставалась кратной, iона должна содержать остаток шариков по модулю i.

Предыдущее объяснение (по ссылке @ xnor): Наивный подход - это метод «обратного воспроизведения». При этом используется наблюдение о том, что в процессе игры опустошается чашка, поэтому при обратной игре собирают бусинки из каждой чашки и помещают их в первую пустую чашку, вот так (63 байта):

f=n=>n?[...a=f(n-1),0].some((m,i)=>(m?a[i]--:a[i]=i+1)>m)&&a:[]

Теперь рассмотрим первые iчашки. В случае, если один из них пуст, обратное воспроизведение добавит 1к общему количеству бус в этих чашках, в то время как в случае, если ни один из них не пуст, обратное воспроизведение вычтет iиз общей суммы, однако это эквивалентно добавлению 1по модулю. i+1, Следовательно, после nобратного воспроизведения сумма шариков в первых iчашках будет эквивалентна по nмодулю i+1или, другими словами, количество шариков в первой iчашке будет равно nминус сумме шариков в предыдущих чашках по модулю i+1. Теперь для того, чтобы эта iчашка была играбельной, количество шариков не может превышать i, поэтому фактически оно будет равно количеству оставшихся шариков по модулю.i+1, (Обратите внимание, что я использую, d=i+1поскольку он использует меньше байтов.)

Рубин, 36 байт

Порт ответа @ orlp, потому что я слишком гениален, чтобы думать о чем-то лучше.

m=->n,i=2{n>0?[n%i]+m[n-n%i,i+1]:[]}