首页 > ACM题库 > HDU-杭电 > HDU 4577-X-Boxes-高精度-[解题报告]HOJ
2015
09-16

HDU 4577-X-Boxes-高精度-[解题报告]HOJ

X-Boxes

问题描述 :

Crazygirl is a crazy fan of XBOX games. Today, she’s here middle in a competition, in which the winner will be rewarded with an opportunity of working in the XBOX Company as a game testing player. Now, here comes the final game. As Cazygirl get a draw with the other competitor, Lich King, she must beat Lich this time.
The game is quite simple. There are n balls numbered from 1 to n and k boxes B1, B2,…, Bk satisfying following conditions:
1.  With any ball x in box Bi, there must be ball 2x in box Bi+1 if there is a box Bi+1;
2.  With any ball x in box Bi, there must be ball y in box Bi-1 satisfying 2y=x if there is a box Bi-1;
3.  You can’t put a ball in two different boxes at the same time;
4.  Your score is the number of balls in box B1;
5.  The player who get the highest score win the game of course.
So, you should tell Crazygirl the highest score she can get.

输入:

The first line is the number of test cases.
Each test case has one line containing two integers n and k, meaning that there are n balls and k boxes. ( 1≤n≤1010000, 2≤k≤25 )

输出:

The first line is the number of test cases.
Each test case has one line containing two integers n and k, meaning that there are n balls and k boxes. ( 1≤n≤1010000, 2≤k≤25 )

样例输入:

3
10 2
7 5
8 3

样例输出:

4
0
1

第一次用java,居然过了。 X-BoxesX-BoxesX-Boxes

import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args) {
		BigInteger s,n,tmp;int k;
		int cas;
		Scanner cin = new Scanner(System.in);
		cas = cin.nextInt();
		while(cas>0){ cas--;
			n = cin.nextBigInteger();
			k = cin.nextInt();
			s = BigInteger.ZERO;
			int cc = 1;
			for(int i=1;i<k;i++){
				cc*=2;
			}
			while(1==1){
				n = n.divide(BigInteger.valueOf(cc));
				tmp = n.subtract(n.divide(BigInteger.valueOf(2)));
				if(tmp.equals(BigInteger.ZERO)) break;
				s = s.add(tmp);
				n = n.divide(BigInteger.valueOf(2));
			}
			System.out.println(s);
		}
	}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/binwin20/article/details/9880969