http://www.spoj.pl/problems/SQRROOT/
plz help me to find out my bug ... i used normal grouping(2 digits) like pen and paper method. Is this approach correct for this problem ?
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>SQRROOT
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
#define SZ(a) a.size()
#define PB push_back
#define MP make_pair
#define VI vector<int>
#define VS vector<string>
#define FOR(i,a,b) for(i = a; i < b; i++)
#define RFOR(i,b,a) for(i = b-1; i >= a; i--)
#define FORS(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define DEBUG(x) cout<<"----"<<x<<"----"<<endl;
#define all(c) c.begin(),c.end()
template<class X> string A2S(X a) {ostringstream os; os << a; return os.str();}
template<class A> vector<A> S2A(string s,A t) {stringstream is; is << s; vector<A>ret;ret.clear(); while(is>>t) ret.PB(t);return ret;}
template<class A> A gcd(A a, A b) {if(b == 0) return a; return gcd(b,a%b);}
template<class A> void domax(A &a, A b) {if(a < b) a = b;}
template<class A> void domin(A &a, A b) {if(a > b) a = b;}
template<class A> A lcm(A a, A b) {return (a*b)/gcd(a,b);}
typedef long long INT;
#define INF 2147483647
#define INFL 9223372036854775807LL
VS v;
string multi(string &b,string &c){
string a="";
int i,j,k,carry;
i = SZ(b)-1,j = 0,carry = 0;
for(i = i; i >= 0; i--){
k = carry + (b[i]-'0')*(c[j]-'0');
carry = k/10,k %= 10;
a += string(1,k+'0');
}
if(carry) a += string(1,carry+'0');
reverse(all(a));
FOR(i,0,SZ(a)-1) if(a[i] != '0') break;
a = a.substr(i);
return a;
}
string minus1(string &b,string &c){
string a="";
int i,j = SZ(c)-1,k,carry;
if(SZ(b) < SZ(c) ||(SZ(b) == SZ(c) && b[0] < c[0])) return "?";
carry = 0;
for(i = SZ(b)-1; i >= 0 && j >= 0; i--,j--){
k = (b[i]-'0')-(c[j]-'0')-carry;
if(k < 0) carry = 1;
else carry = 0;
k += 10, k %= 10;
a += string(1,k+'0');
}
if(i >= 0){
for(i = i; i >= 0; i--){
k = (b[i]-'0')-carry;
if(k < 0) carry = 1;
else carry = 0;
k += 10, k %= 10;
a += string(1,k+'0');
}
}
if(carry) return "?";
reverse(all(a));
for(i = 0; i < SZ(a)-1; i++) if(a[i] != '0') break;
a = a.substr(i);
return a;
}
int main(){
string a;
int i,t,k;
string tmp,ret,j,tmp1,mn;
cin>>t;
stringstream is;
while(t--){
// cout<<endl;
cin>>a;
v.clear();
if(SZ(a)%2) a = string(1,'0')+a;
for(i = 0; i < SZ(a); i+=2){
v.PB(a.substr(i,2));
}
ret = "",a="";
FOR(i,0,SZ(v)){
a += v[i];
j = string(1,2+'0');
tmp = multi(ret,j);
RFOR(k,10,0){
is.clear(),is<<k,is>>j;
tmp1 = tmp + j;
tmp1 = multi(tmp1,j);
mn = minus1(a,tmp1);
// cout<<a<<" "<<tmp1<<" "<<j<<" "<<mn<<endl;
if(mn[0] != '?'){
ret += j;
if(mn[0] == '0') a = "";
else a = mn;
break;
}
}
}
cout<<ret<<endl;
}
return 0;
}
