#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
struct big_int
{
int nrcif;
int cif[205];
};
big_int emp = {0,{}};
big_int unu = {1,{-1,1}};
big_int aduna(big_int a, big_int b)
{
if(a.nrcif==0)
return b;
if(b.nrcif==0)
return a;
big_int rez;
rez.nrcif=0;
int r=0;
for(int i=1;i<=max(a.nrcif,b.nrcif);i++)
{
if(i<=a.nrcif) r += a.cif[i];
if(i<=b.nrcif) r += b.cif[i];
rez.cif[i] = r%10;
rez.nrcif = i;
r/=10;
}
while(r>0)
{
rez.cif[++rez.nrcif] = r%10;
r/=10;
}
return rez;
}
big_int scadere(big_int a, big_int b)
{
for(int i=1;i<=a.nrcif;i++)
{
int cifb;
if(i<=b.nrcif)
cifb=b.cif[i];
else
cifb=0;
if(a.cif[i]>=cifb)
a.cif[i] -= cifb;
else
{
int j=i+1;
while(a.cif[j]==0)
a.cif[j++]=9;
a.cif[j]--;
a.cif[i] = 10 + a.cif[i] - cifb;
}
}
while(a.cif[a.nrcif]==0)
a.nrcif--;
return a;
}
big_int inm_nrmic(big_int a, int x)
{
if(a.nrcif==0 || x==0)
return emp;
int r=0;
for(int i=1;i<=a.nrcif;i++)
{
r += a.cif[i] * x;
a.cif[i] = r%10;
r/=10;
}
while(r>0)
{
a.cif[++a.nrcif] = r%10;
r/=10;
}
return a;
}
big_int inm10(big_int a, int p10)
{
big_int rez;
rez.nrcif = p10 + a.nrcif;
for(int i=1;i<=p10;i++)
rez.cif[i] = 0;
for(int i=1;i<=a.nrcif;i++)
rez.cif[p10+i] = a.cif[i];
return rez;
}
big_int inm_nrmari(big_int a, big_int b)
{
if(a.nrcif==0 || b.nrcif==0)
return emp;
big_int rez = emp;
for(int i=1;i<=b.nrcif;i++)
{
rez = aduna(rez, inm10(inm_nrmic(a,b.cif[i]), i-1));
}
return rez;
}
bool compara(big_int a, big_int b)///return 1 daca a<=b
{
if(a.nrcif < b.nrcif)
return 1;
if(a.nrcif > b.nrcif)
return 0;
for(int i=a.nrcif;i>0;i--)
{
if(a.cif[i] < b.cif[i])
return 1;
if(a.cif[i] > b.cif[i])
return 0;
}
return 1;
}
void afis(big_int a)
{
for(int i=a.nrcif;i>0;i--)
cout<<a.cif[i];
cout<<"\n";
}
big_int citeste()
{
string s;
cin>>s;
big_int rez;
rez.nrcif = 0;
for(int i = (int)s.size()-1;i>=0;i--)
rez.cif[++rez.nrcif] = s[i]-'0';
return rez;
}
void solve_mici(int n)
{
int nrs=sqrt(2LL*(n-1));
nrs = max(0LL, nrs-5);
for(int i=nrs;i<=2e9;i++)
{
if(i*(i+1)<=2LL*(n-1))
{
nrs=i;
}
else
break;
}
//cout<<n<<" "<<1LL + (n-1)*2LL - nrs<<"\n";
cout<<n*2LL - nrs - 1<<"\n";
//cout<<n<<" "<<nrs<<"\n";
}
signed main()
{
//solve_mici(129834123);return 0;
/*big_int a = {5,{-1,1,9,3,4,5}};
big_int b = {3,{-1,8,7,6}};
afis(a);
afis(b);
cout<<"a+b = ";afis(aduna(a,b));
cout<<"a*b = ";afis(inm_nrmari(a,b));*/
big_int n = citeste();
//afis(inm_nrmic(scadere(n,unu),2));
//return 0;
big_int nrs = emp;
for(int i=100;i>=0;i--)
{
for(int j=9;j>0;j--)
{
big_int news = aduna(nrs,inm10({1,{-1,j}},i));
//continue;
if(compara(inm_nrmari(news,aduna(news,unu)), inm_nrmic(scadere(n,unu),2)))
{
nrs = news;
break;
}
}
}
//afis(nrs);
//afis(inm_nrmic(n,2));
//afis(aduna(nrs,unu));
afis(scadere(inm_nrmic(n,2),aduna(nrs,unu)));
return 0;
}
/**
nrs * (nrs+1) / 2 <= n
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
348 KB |
Output is correct |
| 2 |
Correct |
22 ms |
468 KB |
Output is correct |
| 3 |
Correct |
22 ms |
604 KB |
Output is correct |
| 4 |
Correct |
21 ms |
348 KB |
Output is correct |
| 5 |
Correct |
22 ms |
348 KB |
Output is correct |
| 6 |
Correct |
22 ms |
348 KB |
Output is correct |
| 7 |
Correct |
21 ms |
348 KB |
Output is correct |
| 8 |
Correct |
21 ms |
348 KB |
Output is correct |
| 9 |
Correct |
22 ms |
348 KB |
Output is correct |
| 10 |
Correct |
22 ms |
348 KB |
Output is correct |
| 11 |
Correct |
24 ms |
348 KB |
Output is correct |
| 12 |
Correct |
21 ms |
460 KB |
Output is correct |
| 13 |
Correct |
22 ms |
460 KB |
Output is correct |
| 14 |
Correct |
25 ms |
464 KB |
Output is correct |
| 15 |
Correct |
22 ms |
348 KB |
Output is correct |
| 16 |
Correct |
23 ms |
468 KB |
Output is correct |
| 17 |
Correct |
26 ms |
348 KB |
Output is correct |
| 18 |
Correct |
24 ms |
344 KB |
Output is correct |
| 19 |
Correct |
23 ms |
344 KB |
Output is correct |
| 20 |
Correct |
27 ms |
348 KB |
Output is correct |
| 21 |
Correct |
23 ms |
468 KB |
Output is correct |
| 22 |
Correct |
25 ms |
348 KB |
Output is correct |
