### Saratov State University :: Online Contester

::Go
- home
- news
- register
 - update personal info
 - problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- projects

 ::Poll Are you registered on Codeforces?YesNoWhat is it???[results]

::webboard

 why TLE on test 25?
Author: ata
ID: 059912
Problem: 111
Contest: 0
Date: 2014-09-30 07:21:06

#include<bits/stdc++.h>

using namespace std;

const int Maxn=1000+3;

struct bignum
{
int num,d[Maxn];

bignum()
{
memset(d,0,sizeof d);
num=0;
}
//init with 0

bignum (string s)
{
memset(d,0,sizeof d);
num=s.length();
for(int i=0;i<num;i++)
d[i]=s[num-1-i]-'0';
}
//init with integer

bignum (int ch)
{
int t=ch,p=0;
memset(d,0,sizeof d);
while(t)
{
d[p++]=t%10;
t/=10;
}
num=p;
if(ch==0)
num=1;
}

bignum operator +(const bignum &second)const
{
bignum res;
for(int i=0;i<max(second.num,num);i++)
res.d[i]=d[i]+second.d[i];
for(int i=0;i<max(num,second.num)+3;i++)
if(res.d[i])
{
res.num=i+1;
res.d[i+1]+=res.d[i]/10;
res.d[i]%=10;
}
return res;
}
//sum operator

bignum operator +(const int &second)const
{
bignum res=*this;
res.d[0]++;
for(int i=0;res.d[i]>=10;i++)
{
res.d[i+1]+=res.d[i]/10;
res.d[i]%=10;
}
if(res.d[num])
res.num++;
return res;
}

bignum operator *(const bignum &second)const
{
bignum res;
for(int i=0;i<num;i++)
for(int j=0;j<second.num;j++)
res.d[i+j]+=d[i]*second.d[j];
for(int i=0;i<Maxn;i++)
if(res.d[i])
{
res.d[i+1]+=res.d[i]/10;
res.d[i]%=10;
res.num=i+1;
}
return res;

}
//multiple operator

bignum operator /(const int second)const
{
bignum res;
int t=0,q=0;
for(int p=num-1;p>=0;p--)
{
t=t*10+d[p];
res.d[q++]=t/2;
t%=2;
}
reverse(res.d,res.d+q);
res.num=q;
if(res.d[q-1]==0)
res.num--;
return res;
}
// division operator

bool operator <=(const bignum &second)const
{
if(num>second.num)
return false;
if(num<second.num)
return true;
for(int i=num-1;i>=0;i--)
if(d[i]>second.d[i])
return false;
else if(d[i]<second.d[i])
return true;

return true;
}

bignum operator -(const int &second)const
{
bignum res;
res=*this;
int p=0;
while(!res.d[p])
p++;
res.d[p]--;
for(int i=0;i<p;i++)
res.d[i]=9;
if(!res.d[num-1])
res.num--;
return res;

}

bool operator ==(const bignum &second)const
{
if(num!=second.num)
return false;
for(int i=0;i<num;i++)
if(d[i]!=second.d[i])
return false;
return true;
}

bool operator <(const bignum &second)const
{
if(num>second.num)
return false;
if(num<second.num)
return true;
for(int i=num-1;i>=0;i--)
if(d[i]<second.d[i])
return true;
else if(d[i]>second.d[i])
return false;

return false;
}

void print()
{
for(int i=num-1;i>=0;i--)
printf("%d",d[i]);
printf("n");
}
/* void printerr()
{
for(int i=num-1;i>=0;i--)
cerr<<d[i];
cerr<<endl;
}*/

void get()
{
char str[1005];
scanf("%s", str);
num = 0;
for(int i = 0; str[i]; i++){
d[i] = str[i] - '0';
num++;
}
reverse(d, d + num);
}
};

bignum n;
inline void input()
{
n.get();
}

inline void output()
{
bignum f(1),l(2);
while(f*f<n)
f=f*l;
l=f;
f=f/2;
while(f<=l)
{
bignum mid=(f+l)/2;
if(mid*mid==n)
{
mid.print();
return;
}
if(mid*mid<n&&n<(mid+1)*(mid+1))
{
mid.print();
return;
}
if(mid*mid<n)
f=mid+1;
else
{
l=mid-1;
}
}

f.print();

}

int main()
{
ios_base::sync_with_stdio(false);
bignum o("1"),O("2"),OO("3");
input();
if(n==o||n==O||n==OO)
cout<<1;
else
output();
return 0;
}