首页 > 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


  1. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  2. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  3. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  4. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  5. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  6. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  7. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我

  8. 你说你自己吧 大哈卵 评论都看不懂还回复你妹呀 我说让你尊重台湾配音员 谁他妈和你说爱国 自己傻逼 就别说人家 把我归类成你的同类简直是侮辱我