ZOJ Problem Set - 1380
Before computers were widely used, there was another fairly convenient way of archiving data, where librarians archived periodicals on microfiches. A microfiche is a rectangular card made of high-resolution magnet that can store the image of a newspaper page on an area as small as one square millimeter. One may view the newspaper from a microfiche by a device with strong magnification capability. In order to keep a large microfiche collection in perfect order and provide good search service to the users, Gholam, one ingenious librarian, invented a microfiche storage machine.
There are n microfiches in the collection, and each of them has a unique id number. There is a catalogue that allows one to easily find the id number of the microfiche desired.
Gholam proposes to put each microfiche in a special frame, as shown in the figure below. The upper left corner of the frame is clipped, to make sure that there is only one orientation possible for a framed microfiche in its stack (explained below).
The id number of a microfiche is encoded, in binary, on the frame as follows. Let g be the number of bits necessary to represent an id number, indexed from 0 to g - 1. The left side of the frame contains g information cells. A "1" is represented as a dent on the information cell, and a "0" is represented as a hole. The first (uppermost) information cell corresponds to the most significant bit of the id number; the last information cell corresponds to its least significant bit. See the above figure for an illustration.
The microfiche storage machine contains three stacks, stack 0, stack 1, and stack 2, capable of holding n microfiches each. If you look at these stacks from the top, each of them is shaped like a rectangle with the upper left corner clipped. Initially, stack 0 is used for storage of microfiches; stacks 1 and 2 are only used for performing the move operation described below. The machine used to perform more operations, but move is the only operation that is considered in this problem.
move (i, k, j): This operation moves all the microfiches with a "0" in information cell k (0 k g - 1) from stack i to the top of stack j such that the original relative ordering of the pulled microfiches from stack i , and that of the ones originally in stack j are preserved. In practice, a rod is inserted through all the holes (encoded "0"s) and dents (encoded "1"s) of the information cells in position k. Then the machine pulls the rod to the left, and thus the microfiches that have a hole (a "0") at position k will be pulled out (e.g. the microfiche of Figure 2.A), but those which have a dent ("1") in position k (e.g. Fig 2.B) would be left in the stack.
Gholam wants to find a certain microfiche with a known id number. He achieves this goal by performing a sequence of move operations, such that after performing the operations, there will be one stack that holds the desired microfiche only. Your task is to write a program to find the minimum length of such a sequence.
Source: Asia 2002, Tehran (Iran), Preliminary