|Online Judge||Problem Set||Authors||Online Contests||User|
Tower of Hanoi
The Tower of Hanoi is a puzzle consisting of three pegs and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg, obeying the following rules:
For n disks, it is a well-known result that the optimal solution takes 2n − 1 moves.
To complicate the puzzle a little, we allow multiple disks to be of the same size. Moreover, equisized disks are mutually distinguishable. Their ordering at the beginning should be preserved at the end, though it may be disturbed during the process of solving the puzzle.
Given the number of disks of each size, compute the number of moves that the optimal solution takes.
The input contains multiple test cases. Each test case consists of two lines. The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 106). The second lines contains n integers a1, a2, …, an (1 ≤ a1, a2, …, an ≤ 105). For each 1 ≤ i ≤ n, there are ai disks of size i. The input ends where EOF is met.
For each test case, print the answer modulo m on a separate line.
1 1000 2 5 1000 1 1 1 1 1 5 1000 2 2 2 2 2 5 1000 1 2 1 2 1
3 31 123 41
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
Any problem, Please Contact Administrator