2012年9月8日

UVa 10023 - Square root


import java.math.BigInteger;
import java.util.Scanner;

public class Main {
  public static int lowSqrt(int n) {
    int i;
    for (i = 10; i >= 0; i--)
      if ((i * i) <= n) break;
    return i;
  }

  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    while (n > 0) {
      n--;
      String s = cin.next();
      int i;
      BigInteger tmp, cal;
      if (s.length() % 2 == 1) tmp = BigInteger.valueOf(s.charAt(0) - '0');
      else tmp = BigInteger.valueOf((s.charAt(0) - '0') * 10 + s.charAt(1) - '0');
      cal = BigInteger.valueOf(lowSqrt(tmp.intValue()));
      tmp = tmp.subtract(cal.multiply(cal));
      System.out.print(cal);
      cal = cal.add(cal);
      for (i = 2 - (s.length() % 2); i < s.length(); i += 2) {
        tmp = tmp.multiply(BigInteger.valueOf(100)).add(BigInteger.valueOf((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0'));
        int run;
        BigInteger temp = BigInteger.valueOf(0);
        for (run = 9; run >= 0; run--) {
          temp = cal.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(run)).multiply(BigInteger.valueOf(run));
          if (temp.compareTo(tmp) <= 0) {
            tmp = tmp.subtract(temp);
            cal = cal.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(run * 2));
            break;
          }
        }
        System.out.print(run);
      }
      System.out.println("");
      if (n > 0) System.out.println("");
    }
  }
}

沒有留言:

張貼留言