#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
string fix(string s){
int i=0;
for(1;i<s.size();i++){
if(s[i]!='0'){
break;
}
}
string s2;
for(int j=i;j<s.size();j++){
s2+=s[j];
}
return s2;
}
string sum(string s, string s2){
if(s2.size()>s.size()){string h=s;s=s2;s2=h;}int p=s.size()-s2.size();
for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
int n=s.size(),m=s2.size(),k;int i=n-1,j=m-1;
while(1){int a=s[i]-'0';int b=0;if(j>=0)b=s2[j]-'0';
if((a+b+c)>9){k=(a+b+c)%10;c=1;}
else{k=a+b+c;c=0;}char p=k+'0';ans=p+ans;
if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
return fix(ans);
}
string multi(string s, string s2){
string ans="0";int n=s.size();int m=s2.size();int l=0;
for(int i=n-1;i>=0;i--){string pre;int c=0;for(int j=m-1;j>=0;j--){
int a=s[i]-'0',b=s2[j]-'0';int k=(a*b+c)%10;char p=k+'0';pre=p+pre;c=(a*b+c)/10;
}
if(c!=0){
char p=c+'0';
pre=p+pre;
}
for(int j=0;j<l;j++){
pre=pre+'0';
}
l++;
ans=sum(ans,pre);
}
return fix(ans);
}
string divide(string s){
string ans;int c=0;
for(int i=0;i<s.size();i++){int a=s[i]-'0';int k=c*10+a;
char p=(k/2)+'0';
c=k%2;ans=ans+p;
}return fix(ans);
}
int check(string s, string s2){
if(s.size()>s2.size())return 0;
else if(s.size()<s2.size())return 1;
else {
if(s>s2 )return 0;
else return 1;
}
}
bool isSmaller(string str1, string str2)
{
// Calculate lengths of both string
int n1 = str1.length(), n2 = str2.length();
if (n1 < n2)
return true;
if (n2 < n1)
return false;
for (int i = 0; i < n1; i++)
if (str1[i] < str2[i])
return true;
else if (str1[i] > str2[i])
return false;
return false;
}
// Function for find difference of larger numbers
string findDiff(string str1, string str2)
{
// Before proceeding further, make sure str1
// is not smaller
if (isSmaller(str1, str2))
swap(str1, str2);
// Take an empty string for storing result
string str = "";
// Calculate length of both string
int n1 = str1.length(), n2 = str2.length();
// Reverse both of strings
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
// Run loop till small string length
// and subtract digit of str1 to str2
for (int i = 0; i < n2; i++) {
// Do school mathematics, compute difference of
// current digits
int sub
= ((str1[i] - '0') - (str2[i] - '0') - carry);
// If subtraction is less than zero
// we add then we add 10 into sub and
// take carry as 1 for calculating next step
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
// subtract remaining digits of larger number
for (int i = n2; i < n1; i++) {
int sub = ((str1[i] - '0') - carry);
// if the sub value is -ve, then make it positive
if (sub < 0) {
sub = sub + 10;
carry = 1;
}
else
carry = 0;
str.push_back(sub + '0');
}
// reverse resultant string
reverse(str.begin(), str.end());
return str;
}
string sq(string a){
string lo="0";
string hi="1";
for(int i=1;i<=102;i++){
hi+='0';
}
while(check(lo,hi)){
string mid=sum(lo,hi);
mid=(divide(mid));
string t=multi(mid,mid);
if(check(a,t)==0){
lo=sum(mid,"1");
}
else{
hi=findDiff(mid,"1");
}
}
if(multi(lo,lo)==a){
return lo;
}
else{
return hi;
}
return lo;
}
signed main(){
string n;
cin>>n;
string h=sq(multi(n,"2"));
//cout<<divide(multi(h,(sum(h,"1"))));
if( isSmaller(divide(multi(h,(sum(h,"1")))),n) )h=sum(h,"1");
cout<<fix(findDiff(multi(h,h), multi( findDiff( divide(multi(h,sum(h,"1"))),n ),"2" ) ));
}
Compilation message
oddeven.cpp: In function 'std::string fix(std::string)':
oddeven.cpp:10:9: warning: statement has no effect [-Wunused-value]
10 | for(1;i<s.size();i++){
| ^
oddeven.cpp:10:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(1;i<s.size();i++){
| ~^~~~~~~~~
oddeven.cpp:16:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int j=i;j<s.size();j++){
| ~^~~~~~~~~
oddeven.cpp: In function 'std::string sum(std::string, std::string)':
oddeven.cpp:23:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
23 | for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
| ^~~
oddeven.cpp:23:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
23 | for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
| ^~~~~~
oddeven.cpp:28:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
28 | if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
| ^~
oddeven.cpp:28:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
28 | if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
| ^
oddeven.cpp: In function 'std::string divide(std::string)':
oddeven.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<s.size();i++){int a=s[i]-'0';int k=c*10+a;
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
348 KB |
Output is correct |
| 2 |
Correct |
101 ms |
348 KB |
Output is correct |
| 3 |
Correct |
95 ms |
348 KB |
Output is correct |
| 4 |
Correct |
96 ms |
344 KB |
Output is correct |
| 5 |
Correct |
95 ms |
428 KB |
Output is correct |
| 6 |
Correct |
101 ms |
348 KB |
Output is correct |
| 7 |
Correct |
97 ms |
348 KB |
Output is correct |
| 8 |
Correct |
95 ms |
348 KB |
Output is correct |
| 9 |
Correct |
96 ms |
348 KB |
Output is correct |
| 10 |
Correct |
97 ms |
348 KB |
Output is correct |
| 11 |
Correct |
97 ms |
348 KB |
Output is correct |
| 12 |
Correct |
102 ms |
424 KB |
Output is correct |
| 13 |
Correct |
100 ms |
348 KB |
Output is correct |
| 14 |
Correct |
106 ms |
344 KB |
Output is correct |
| 15 |
Correct |
98 ms |
428 KB |
Output is correct |
| 16 |
Correct |
119 ms |
424 KB |
Output is correct |
| 17 |
Correct |
107 ms |
428 KB |
Output is correct |
| 18 |
Correct |
152 ms |
432 KB |
Output is correct |
| 19 |
Correct |
120 ms |
348 KB |
Output is correct |
| 20 |
Correct |
118 ms |
348 KB |
Output is correct |
| 21 |
Correct |
121 ms |
348 KB |
Output is correct |
| 22 |
Correct |
132 ms |
348 KB |
Output is correct |
