Sqrt Bo

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 145 Accepted Submission(s): 72

Problem Description

Let's define the function f(n)=⌊n−−√⌋.

Bo wanted to know the minimum number y which satisfies fy(n)=1.

note:f1(n)=f(n),fy(n)=f(fy−1(n))

It is a pity that Bo can only use 1 unit of time to calculate this function each time.

And Bo is impatient, he cannot stand waiting for longer than 5 units of time.

So Bo wants to know if he can solve this problem in 5 units of time.

Input

This problem has multi test cases(no more than 120).

Each test case contains a non-negative integer n(n<10100).

Output

For each test case print a integer - the answer y or a string "TAT" - Bo can't solve this problem.

Sample Input

233
233333333333333333333333333333333333333333333333333333333

Sample Output

TAT

直接java暴力

import java.math.*;

import java.util.*;

public class Main{

    /**

     * @param args

     */

    public static void main(String[] args) {

        Scanner cin=new Scanner(System.in);

        BigDecimal n;

        BigDecimal tmp=new BigDecimal("10");

        BigDecimal tmpp=new BigDecimal("0");

        MathContext mc = new MathContext(1000,RoundingMode.HALF_DOWN);

        int ans;

        while(cin.hasNext()){

            ans=-1;

            n=cin.nextBigDecimal();

            if(n.compareTo(tmpp)==0){

                System.out.println("TAT");continue;

            }

            for(int j=1;j<=5;j++){

                BigDecimal d = new BigDecimal(Math.sqrt(n.doubleValue()),mc);

                n=d;

                if(n.compareTo(tmp)<0){

                    if(n.intValue()==1){

                        ans=j;break;

                    }

                }

            }

            if(ans!=-1)System.out.println(ans);

            else System.out.println("TAT");

        }

    }

}

bo

HDU 5752Sqrt Bo

Sqrt Bo