Testing shuffle machines

Sergei Mikhailovich has a very interesting job. He tests shuffle machines—mechanisms used for shuffling stacks of cards.

The machines that Sergei Mikhailovich tests perform permutations of a stack of $n$ cards, where $n$ is an even natural number. The way they work is to apply to the original stack a given sequence of transformations, each of which is of one of two types: U or D.

A U-transformation is performed as follows. First, the initial stack of $n$ cards is divided into two parts: the first part consists of the top $n/2$ cards, and the second part consists of the bottom $n/2$ cards. Then, the resulting stack is formed by alternately placing one card from each of the two parts, starting with the first part. The D-transformation differs only in that, at the second step, the resulting stack starts with the second part instead of the first.

If we number the cards from top to bottom as 1, 2, \ldots, n, then after a U-transformation, the cards from top to bottom will be arranged in the following order: 1, n/2+1, 2, n/2+2, \ldots, n/2, n. After a D-transformation, the order will be: n/2+1, 1, n/2+2, 2, \ldots, n, n/2.

Sergei Mikhailovich tests machines as follows. He takes $n$ cards numbered from $1$ to $n$, arranges them in a stack so that their numbers increase from top to bottom, places the stack in the machine, and performs the shuffling. Then Sergei Mikhailovich takes the $k$-th card from the top in the resulting stack and, depending on its number, decides whether the machine is working properly or not.

To speed up testing, Sergei Mikhailovich needs a program to compute the number of the $k$-th card from the top in the resulting stack, provided the shuffle machine is working correctly.