Problem #184

Tubes 2
Public 11/17/14 24xp Programming 66.7%

See p180 from Sinan. Now there are 10 tubes named with A,B,C,D,E,F,G,H,I,J with capacities 14,13,12,12,10,10,7,7,7,7 respectively. The first state is (A to J) 10,9,11,10,9,8,5,5,4,2. The goal state is (A to J) 13,12,11,11,4,6,6,0,6,4. Encode each state as a hex number JIHGFEDCBA, so the starting state is 245589AB9A, the ending state is 460664BBCD.

We need to reach to the goal state with the mimimum number of steps.

Let A be the eventual array of size k with the states (from first to last) in it:
A=[245589AB9A,...,460664BBCD]
where A[i] is the state at the i-th phase, i=1,..,k

Let N be the hex number obtained by concatenating the hex digits of the above array:
N=245589AB9A...460664BBCD or
N=A[1]*B^(k-1)+A[2]*B^(k-2)+...+A[k]*B^0 where B=16^10=2^40

Find the smallest N.
(i.e. Find the lexicographically first, shortest path.)

Answer format: N Mod 1000000007

My timing: 60 sec. [[using less than 1GB of Ram]]



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]