/*
NOIP 2011 普及组初赛试题完善程序4.2
(大整数开方) 输入一个正整数n（1≤n≤10100），
试用二分法计算它的平方根的整数部分。

大整数开方技巧
https://blog.csdn.net/cprimesplus/article/details/83351103

大数开方(C++版)
https://blog.csdn.net/ACdreamers/article/details/8885090

CCF NOI1154 大整数开方
https://blog.csdn.net/tigerisland45/article/details/71699566
*/
#include<iostream>
#include<string>
using namespace std;

const int SIZE=200;
struct hugeint{
    int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推

hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for(i=1;i<=a.len;i++)
       for(j=1;j<=b.len;j++)
            [      ①     ] +=a.num[i]*b.num[j]; //ans.num[i+j-1] 
    for(i=1;i<=a.len+b.len;i++){
        ans.num[i+1]+=ans.num[i]/10;
        [         ②         ]; //ans.num[i]%=10;
    }
    if(ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}

hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if(a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for(i=1;i<=ans.len;i++){
        ans.num[i]+= [        ③      ] ; //a.num[i]+b.num[i]
        ans.num[i+1]+= ans.num[i]/10;
        ans.num[i]%=10;
    }
    if(ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}

hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
    int i;
    hugeint ans;
    ans=add(a,b);
    for(i=ans.len;i>=2;i--){
        ans.num[i-1]+=([     ④      ])*10; 
        //ans.num[i] % 2
        ans.num[i]/=2;
    }
    ans.num[1]/=2;
    if(ans.num[ans.len]==0)
        ans.len--;
    return ans;
}

hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
    int i;
    hugeint ans;
    ans=a;
    ans.num[1]+=2;
    i=1;
    while( (i<=ans.len)&&(ans.num[i]>=10) ){
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }
    if(ans.num[ans.len+1]>0)
        [      ⑤    ]; //ans.len++
    return ans;
}

bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
    int i;
    if([      ⑥     ]) //a.len<b.len
        return false;
    if( a.len>b.len )
        return true;
    for(i=a.len;i>=1;i--){
        if(a.num[i]<b.num[i])
           return false;
        if(a.num[i]>b.num[i])
           return true;
    }
    return false;
}

int main()
{
    string s;
    int i;
    hugeint target,left,middle,right;
    cin>>s;
    memset(target.num,0,sizeof(target.num));
    
	target.len=s.length();
    
    
	for(i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-[      ⑦    ];//'0' 48
    
	memset(left.num,0,sizeof(left.num));
    
    其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
	left.len=1;
    left.num[1]=1;
    right=target;
    
	do{
        middle=average(left,right);
        // 若大整数a>b则返回true，否则返回false
		if(over([       ⑧        ]))
		//times(middle,middle),target
		// 计算大整数a和b的乘积
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right) );
    
	for(i=left.len;i>=1;i--)
       cout<<left.num[i];
    
	return 0;
}
/*
1.正确答案： ans.num[i+j-1]

2.正确答案： ans.num[i]%=10

3.正确答案： a.num[i]+b.num[i]

4.正确答案： ans.num[i] % 2

5.正确答案： ans.len++

6.正确答案： a.len<b.len

7.正确答案： '0' / 48

8.正确答案： times(middle,middle),target
*/

---

---

---

---

---

---

---

---

---

CSP-J1 CSP-S1 第1轮 初赛 相关的在线测试网站

洛谷有题

试题列表 - 洛谷有题

信息学奥赛普及组初赛试题评测题库

信息学奥赛一本通（C++版）在线评测系统

信息学奥赛提高组初赛试题评测题库

信息学奥赛一本通（C++版）在线评测系统

有道小图灵 信息学

信息学奥赛-NOIP-少儿编程培训-有道小图灵

信奥题库

信奥题库 - OITIKU.com

牛客网初赛

比赛历年真题_CSP-J入门组/CSP-S提高组/NOI/省选/USACO/信息学教材_牛客竞赛OJ