HDU 5752 Sqrt Bo

Sqrt Bo

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

Problem Description

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

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

note:f¹(n)=f(n),f^y(n)=f(f^y-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<10¹⁰⁰).

 

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

3

TAT

 

Source

2016 Multi-University Training Contest 3

 

解析：题意为给定一个数n(0 ≤ n < 10¹⁰⁰)，不断地开方并向下取整，问经过多少次操作后n等于1。当操作次数大于5时输出"TAT"，当操作次数小于或等于5时输出操作的次数。因为有5次的限制，我们可以找到一个分界点。易知这个分界点为2³²：当n≥2³²时，输出"TAT"（当n==0时也输出"TAT"），其他情况与2的对应次幂比较即可。

#include <bits/stdc++.h>
#define ll long long

char s[105];

int main()
{
    while(~scanf("%s", s)){
        int len = strlen(s);
        if(len>10){
            puts("TAT");
            continue;
        }
        ll sum = 0;
        for(int i = 0; i < len; ++i)
            sum = sum*10+s[i]-'0';
        if(sum >= 1ll<<32 || sum == 0) puts("TAT");
        else if(sum >= 1ll<<16) puts("5");
        else if(sum >= 1ll<<8) puts("4");
        else if(sum >= 1ll<<4) puts("3");
        else if(sum >= 1ll<<2) puts("2");
        else if(sum >= 1ll<<1) puts("1");
        else puts("0");
    }
    return 0;
}