# [ccNOV14] Chef and Segment Game

## 描述 Description

Chef loves to play games. Now he plays very interesting game called “Segment”. At the beginning Chef has segment [0, X] and no points on it. On each step Chef chooses the subsegment of maximal length possible such as it contains no points on it. If there are more than one such subsegment Chef chooses the one with the minimal left coordinate. Once Chef chosed the subsegment he put the point in it’s middle and the step is over.

Help Chef to define the coordinate of the point he will put on the K-th step.

## 输入格式 InputFormat

The first line contains integer T - number of test cases.

Each of next T lines contains two integers X and K.

## 输出格式 OutputFormat

For each test case in a single line print single double number - the coordinate of the K-th point Chef will put. Answer will be considered as correct if absolute difference between the answer and correct answer is less or equal 10^(-6).

## 样例输入 SampleInput

4
10 1
10 2
10 3
1000000000 1234567

## 样例输出 SampleOutput

5.0000
2.5000
7.5000
177375316.6198730500000000

CodeChef CHEFSEG

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
ll i,j,t,n,m,l,r,k,z,y,x;
ll f[45];
double ans,d;
ll T;
int main()
{
f[0]=t=1;
for (i=1;i<=40;i++) t*=2,f[i]=f[i-1]+t;
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lld",&x,&k);
t=(int)((double)log(k)/(double)log(2));
d=(double)x/(double)(f[t]+1);
ans=d*((k-((t>0)?f[t-1]:0))*2-1);
printf("%.7lf\n",ans);
}
return 0;
}``````