Ханойская башня — это известная математическая головоломка. Она состоит из трех стержней и нескольких дисков различных размеров, каждый диск можно нанизывать на любой стержень. В начале диски аккуратно нанизаны на один из стержней по возрастанию размера, самый маленький диск сверху, таким образом образуя форму конуса.
Цель головоломки — перенести всю стопку дисков на другой стержень, соблюдая следующие простые правила:
- За один ход можно переместить только один диск.
- Каждый ход заключается в том, что мы берем верхний диск с одного стержня и помещаем его сверху на другой стержень. То есть диск можно перемещать, только если он верхний в стопке.
- Никакой диск нельзя класть на диск меньшего размера.
С тремя дисками головоломка решается в семь ходов. Наименьшее количество ходов, необходимое для решения головоломки про Ханойскую башню равняется 2n - 1, где n — количество дисков. (c) перевод английской статьи из Wikipedia.
Головоломка SmallR очень похожа на Ханойскую башню. В Ханойской башне вам требуется переместить все диски на другой стержень за минимальное количество ходов. В головоломке SmallR каждый ход стоит некоторое количество денег, и вам надо решить ту же самую головоломку за минимальную стоимость. При этом в начале все n дисков находятся на первом стержне. Перемещение диска со стержня i на стержень j (1 ≤ i, j ≤ 3) стоит tij единиц денег. Цель головоломки в том, чтобы переместить все диски на третий стержень.
В этой задаче вам дана матрица t и целое число n. Надо посчитать наименьшую стоимость решения головоломки SmallR с n дисками.