Problem:


無限急行

ムゲン鉄道のムゲン線には無限個の駅があります。駅には …, -3, -2, -1, 0, 1, 2, 3, … と番号が振られていて、各駅は数直線上の整数と同じ順番で隣り合っています。あなたはいま、ある番号の駅から電車に乗り、それより大きな番号の駅に向かおうとしています。

ムゲン線には無限種類の快速電車が走っています。それらは 0 級快速、1 級快速、2 級快速、3 級快速、… のように番号で呼ばれています。n 級快速の電車は、2n の倍数の番号の駅に停車します。たとえば、1級快速は駅 …, -4, -2, 0, 2, 4, … に、3 級快速は駅 …, -24, -16, -8, 0, 8, 16, 24, … に停車するといった具合です。0 級快速はすべての駅に停車するので、本当は各駅停車ですがムゲン鉄道は「快速」と呼んでいます。

どの級の快速電車も、ある停車駅から次の停車駅まで移動するのに1単位時間かかります。また、快速電車間の乗り換えにかかる時間は無視できるものとします。乗車駅 s と降車駅 d が与えられたとき、s から d へ移動するのに必要な最小の時間を求めるプログラムを作成してください。ただし、s から d へ移動する間に、大きな番号から小さな番号の駅に向かっての移動は認められないものとします。

入力

入力は1つのデータセットからなる。入力データは以下の形式で与えられる。

N
s1 d1
s2 d2
:
sN dN

１行目に移動の回数を表す N (1 ≤ N ≤ 100) が与えられる。続く N 行に、乗車駅の番号 si と降車駅の番号 di (-1,000,000,000 ≤ si < di ≤ 1,000,000,000) が与えられる。

出力

与えられた乗車駅と降車駅ごとに、移動に必要な最小の時間を１行に出力する。

入出力例

入力例

3
0 7
-1048576 0
-3 5

出力例

3
1
4



Sample input:
3
0 7
-1048576 0
-3 5


Sample output:
3
1
4

Submission status: Accepted

Solution code:
def calc(start, end, n):
    if start % 2 == 1:
        n += 1
        start += 1
    if end % 2 == 1:
        n += 1
        end -= 1

    if start != end:
        n += calc(start/2, end/2, 0)

    return n

for i in range(input()):
    line = [int(x) for x in raw_input().split(" ")]
    print calc(line[0], line[1], 0)

Submission status: Accepted

Solution code:
# AOJ 0289: Infinite Express
# Python3 2018.6.23 bal4u

def calc(s, d):
	if s == d: return 0;
	ans = 0
	if s % 2 != 0:
		ans += 1
		s += 1
	if d % 2 != 0:
		ans += 1
		d -= 1
	return ans + calc(s>>1, d>>1);

n = int(input())
for i in range(n):
	s, d = map(int, input().split())
	print(calc(s, d))

Submission status: Accepted

Solution code:
# AOJ 0289: Infinite Express
# Python3 2018.6.23 bal4u

def calc(s, d):
	if s == d: return 0;
	ans = 0
	if s & 1:
		ans += 1
		s += 1
	if d & 1:
		ans += 1
		d -= 1
	return ans + calc(s>>1, d>>1);

n = int(input())
for i in range(n):
	s, d = map(int, input().split())
	print(calc(s, d))

Submission status: Accepted

Solution code:
N = int(input())
for i in range(N):
    s, d = map(int, input().split())
    s += 2**30; d += 2**30
    ans = 0
    while s + (s & -s) <= d:
        s += (s & -s)
        ans += 1
    d -= s
    while d:
        d -= (d & -d)
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


SIZE = 32
POW = [1]*SIZE

for i in range(1,SIZE):
    POW[i] = POW[i-1]*2


N = int(input())

for _ in range(N):
    start,goal = map(int,input().split())
    ans = 0

    rank = 0
    current = start

    while current != goal:
        rank = 0

        for i in range(SIZE-1,0,-1):
            if abs(current)%POW[i] == 0 and current+POW[i] <= goal:
                rank = i
                break
        current += POW[rank]
        ans += 1

    print("%d"%(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Infinite Express
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0289

"""
import sys


def solve(s, d):
    ans = 0
    while s != d:
        step = (s & -s) if s!=0 else 2**32
        while s + step > d:
            step //= 2
        s += step
        ans += 1
    return ans


def main(args):
    N = int(input())
    for _ in range(N):
        s, d = map(int, input().split())
        ans = solve(s, d)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = input()
for loop in range(N):
    s, d = map(int, raw_input().split())
    if s <= 0 <= d:
        print bin(s).count('1') + bin(d).count('1')
        continue
    if d <= 0:
        d, s = -s, -d
    ans = 0
    num = 2
    while s < d:
        if s % num != 0:
            s += num / 2
            ans += 1
        num *= 2
    ans -= 1
    s -= num / 4
    print ans + bin(d - s).count('1')

Submission status: Accepted

Solution code:
def solve(src, dst):
    if src == dst: return 0
    answer = 0
    if src % 2 != 0:
        answer += 1
        src += 1
    if dst % 2 != 0:
        answer += 1
        dst -= 1
    answer += solve(src // 2, dst // 2)
    return answer

N = int(input())
for i in range(N):
    s,d = map(int, input().split())
    print(solve(s,d))

Submission status: Runtime Error

Solution code:
def atob(a, b):
  if a == b:
    return 0
  if a == 0:
    ret = 0
    while b:
      if b % 2:
        ret += 1
      b //= 2
    return ret
  
  acc = 1
  tmp = a
  while tmp:
    if tmp % 2:
      break
    tmp //= 2
    acc *= 2
  return 1 + min(atob(a + acc, b), atob(a - acc, b))

n = int(input())
for _ in range(n):
  s, d = map(int, input().split())
  a, b = abs(s), abs(d)
  a, b = min(a, b), max(a, b)
  if s * d >= 0:
    print(atob(a, b))
  else:
    print(atob(0, a) + atob(0, b))