Problem: stockholm (2018 finals)

Melody is visiting the beautiful city of Stockholm, Sweden! Stockholm has a
number of waterways flowing through it, dividing the city up into a number of
islands. Like most visitors, Melody was surprised to learn that there are in
fact an infinite number of waterways and an infinite number of islands!

The waterways flow between an infinite number of junctions, which are numbered
with non-negative integers starting from 0. There's an infinitely-long
waterway flowing into junction 0, and then for each junction _j_, there are
two waterways flowing out of it into junctions 2_j_+1 and 2_j_+2. This results
in each junction having exactly three incident waterways.

An island is a connected region of land. Each waterway is adjacent to two
different islands (one on each side of it), and has a bridge connecting those
two islands together. Each junction is adjacent to three different islands
(the distinct islands adjacent to its incident waterways).

A portion of Stockholm (including junctions 0 to 14) is illustrated below,
with islands represented as contiguous regions filled with various shades of
grey, and bridges between them represented as brown curves:

![]({{PHOTO_ID:923060468192530}})

Melody is currently aboard a friend's boat parked at some junction **A**, but
she wants to visit another friend's boat which is parked at a different
junction **B**. She'll begin by getting out of the first boat onto any of the
three islands of her choice which are adjacent to junction **A**. She'll then
walk on land until she arrives at any of the three islands which are adjacent
to junction **B**, potentially crossing some bridges between islands along the
way. Finally, she'll board the second boat from that island.

Melody's not a big fan of walking on Stockholm's rather unevenly cobbled
bridges, so she'd like to cross as few of them as possible along the way. Help
her determine the minimum number of bridges which she must cross to walk from
junction **A** to junction **B**!

For example, the following illustration indicates the only optimal path from
junction 8 to junction 5 in red (crossing only 1 bridge), and one of the
optimal paths from junction 12 to junction 3 in yellow (crossing only 2
bridges):

![]({{PHOTO_ID:293195401822038}})

### Input

Input begins with an integer **T**, the number of times Melody needs to travel
between two junctions. For each trip, there is a single line containing the
space-separated integers **A** and **B**.

### Output

For the _i_th trip, output a line containing "Case #_i_: " followed by the
minimum number of bridges which Melody must cross to walk from junction **A**
to junction **B**.

### Constraints

1 ≤ **T** ≤ 2,000  
0 ≤ **A**, **B** ≤ 1018  
**A** ≠ **B**

### Explanation of Sample

The first two cases are described above.

In the third and fourth cases, it's unnecessary for Melody to cross any
bridges.



Sample input:
10
8 5
12 3
0 1
2 10
7 14
424 144
80149 312
123456 654321
672525845223757474 339224993515259183
0 1000000000000000000


Sample output:
Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 0
Case #5: 1
Case #6: 6
Case #7: 3
Case #8: 9
Case #9: 46
Case #10: 16



Code: // Stockholm
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

pair<int,bool> Cost(string s)
{
		if (!Sz(s))
			return(mp(0,0));
	int i=Sz(s)-1;
	// delete equal digits from the end
		while ((i) && (s[i]==s[i-1]))
			i--;
	// delete one more digit from the end
		if (i)
			i--;
	// now empty?
		if (!i)
			return(mp(0,Sz(s)>=2 && s[0]==s[Sz(s)-1]));
	pair<int,bool> c=Cost(s.substr(0,i));
	c.x++;
	return(c);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	LL A,B;
	string X,Y;
	int p,ans;
	pair<int,bool> c1,c2;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			scanf("%lld%lld",&A,&B);
			// convert nodes to binary
			A++,B++;
			X=Y="";
				while (A)
					X=char(A%2+'0')+X,A/=2;
				while (B)
					Y=char(B%2+'0')+Y,B/=2;
			// find LCA
				Fox(p,min(Sz(X),Sz(Y)))
					if (X[p]!=Y[p])
						break;
			// compute costs to LCA
			X=X.substr(p);
			Y=Y.substr(p);
			c1=Cost(X),c2=Cost(Y);
			ans=c1.x+c2.x;
			// at least one node is coming from the outside, and neither is the LCA?
				if ((Sz(X)) && (Sz(Y)) && (c1.y || c2.y))
					ans++;
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}