- Correct output for F1
- Correct output for F2
- Python 3 program solving both subproblems
- Python 3 program to check submissions

The algorithms from this problem have originally been devised for another task: card shuffling. There are two ways to perform a *perfect riffle shuffle* of a deck of cards. (In one of those ways the top card remains on the top, in the other way it becomes the second card from the top.) These two ways of shuffling change the order of a deck of cards in exactly the same way our ferries change the order of the cars in the convoy.

The question from the problem statement then becomes a very natural question: what is the smallest number of (carefully chosen and perfectly executed) riffle shuffles to get a particular card from position *p* to position *q* in the deck?

A nice solution to this problem is described by Sarnath Ramnath and Daniel J. Scully in their paper “Moving card *i* to position *j* with perfect shuffles”.

The general idea of this solution is very simple. Let’s use zero-based indexing, i.e., cards have numbers 0 through 2*n* − 1. Counting modulo 2*n*, a card from position *i* can go to either 2*i* or 2*i* + 1. If we start to draw a tree of possibilities, we will quickly realize that after *k* shuffles the reachable numbers are precisely those in the interval [*i* ⋅ 2^{k}, (*i* + 1)⋅2^{k} − 1]. (Of course, still counting modulo 2*n*. As soon as the length of this interval reaches 2*n*, any value is possible.)

Thus, we have a very simple solution:

- Increment
*k*until our interval hits the desired destination. (This takes*O*(log*n*) steps.) - From the binary value of the offset your destination has within the interval (i.e., from the value “destination minus left boundary of the interval”), reconstruct the right sequence of “times two” and “times two plus one” that gets you from your source to your destination.
- For each individual operation, determine whether it is done by an out-shuffle or an in-shuffle (i.e., an R-ferry or an L-ferry).