Problem #180

Tubes
Public 11/06/14 20xp Programming 50.0%

Consider 6 tubes named A,B,C,D,E,F
with capacities 10,10,7,7,7,7 respectively.

In the first state they contain the following
unit amounts of a certain liquid (A to F):
9, 7, 6, 5, 0, 0

And the goal state is as follows (A to F):
9, 2, 2, 2, 5, 7

Treat each state as a hex number (FEDCBA) and
assign a 6-digit number for them
as in the following example:
The first state=005679
The last state=752229

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=[005679,...,752229]
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=005679...752229 or
N=A[1]*B^(k-1)+A[2]*B^(k-2)+...+A[k]*B^0 where B=16^6

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

Answer format: N Mod 1000000007

Example:
Capacities: 7,6,5,4,4,4
First: 7, 5, 0, 0, 0, 0
Last:  3, 2, 3, 4, 0, 0

1: 7, 5, 0, 0, 0, 0 s=000057
2: 3, 5, 0, 4, 0, 0 s=004053
3: 3, 5, 4, 0, 0, 0 s=000453
4: 3, 6, 3, 0, 0, 0 s=000363
5: 3, 2, 3, 4, 0, 0 s=004323

N = 000057004053000453000363004323 (hex)
N Mod 1000000007 = 10356901 (decimal)

[My timing: 25s]



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]