SGU 111 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=111

111. Very simple problem

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

You are given natural number X. Find such maximum integer number that it square is not greater than X.

Input

Input file contains number X (1≤X≤101000).

Output

Write answer in output file.

Sample Input

16

Sample Output

4

很少做SGU的题目,一直觉得挺有难度的,时间和内存都限制的比较严,测试数据都是高达几十组,不过做SGU的题目确实还是很锻炼人的。SGU的题目描述都很短,简洁明了这个我挺喜欢的(偶是英语盲)。

题意:给出x(1<=x<=10^1000),求出m^2不大于x的最大的m。
分析:初看这道题感觉用java的BigInteger类应该很简单的,不过查了一下才知道,BigInteger提供的成员函数里就是没有开方功能。看来得自己去模拟了。想到的第一个办法是牛顿迭代法,不过试了一下就是不成功。最后决定用二分去做,在0~(x+1)的范围内二分寻找 m 。

codo

import java.io.*;
import java.util.*;
import java.math.*;
 
public class Solution{
    public static void main(String[] argc){
	Scanner in=new Scanner(System.in);
	BigInteger left,right,mid,x,two;
	two=BigInteger.valueOf(2);
	x=in.nextBigInteger();
	left=BigInteger.ZERO;
	right=x.add(BigInteger.ONE);
	while(left.add(BigInteger.ONE).compareTo(right)<0){
	    mid=left.add(right).divide(two);
	    if(mid.multiply(mid).compareTo(x)<=0)
	      left=mid;
	    else
	      right=mid;
	}
	System.out.println(left);
    }
}

另外我还想说一句,SGU的OJ真实超级不人性化。

» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

2 条评论。

  1. 我用你的代码提交MLE.. ==!

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>