#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,goodA,goodB;
string s;
vector<ll> val,va,vb;
void multiply()
{
ll lg=val.size();
int last=lg%2;
if(last==1)
val.push_back(1);
else
val[lg-1]++;
}
void divide()
{
ll lg=val.size();
int last=lg%2;
if(val[lg-1]==1)
val.pop_back();
else
val[lg-1]--;
}
void add()
{
ll lg=val.size();
int last=lg%2;
if(last==0)
{
if(val[lg-1]>1)
{
val[lg-1]--;
val.push_back(1);
}
else
{
assert(lg>=2);
val.pop_back();
lg--;
val[lg-1]++;
}
return;
}
else
{
ll nr1=val[lg-1];
ll nr0=val[lg-2];
val.pop_back();
val.pop_back();
lg-=2;
assert(nr0>0&&nr1>0);
if(nr0==1)
{
val[lg-1]++;
val.push_back(nr1);
}
else
{
nr0--;
val.push_back(nr0);
val.push_back(1);
val.push_back(nr1);
}
}
}
void subtract()
{
int lg=val.size();
int last=lg%2;
if(last==1)
{
if(val[lg-1]==1)
{
lg--;
val.pop_back();
val[lg-1]++;
}
else
{
val[lg-1]--;
val.push_back(1);
}
return;
}
else
{
ll nr0=val[lg-1];
ll nr1=val[lg-2];
val.pop_back();
val.pop_back();
if(nr1==1)
{
val[lg-1]++;
val.push_back(nr0);
}
else
{
nr1--;
val.push_back(nr1);
val.push_back(1);
val.push_back(nr0);
}
}
}
ll getniv(ll x)
{
for(ll d=0;d<=62;d++)
{
ll st=(1LL<<d);
ll dr=st*2LL-1;
if(x>=st&&x<=dr)
return d;
}
return -1;
}
int main()
{
cin>>s;
val.push_back(1);
goodA=1;
ll x=1;
for(char c:s)
{
if(c=='1')
{
multiply();
goodA*=2LL;
x*=2LL;
}
if(c=='2')
{
multiply();
goodA*=2LL;
x*=2LL;
add();
x++;
goodA++;
}
if(c=='U')
{
divide();
x/=2;
goodA/=2;
}
if(c=='L')
{
//subtract();
goodA--;
}
if(c=='R')
{
add();
x++;
goodA++;
}
}
for(int i=0;i<val.size();i++)
{
if(i%2==0)
{
for(int j=1;j<=val[i];j++)
va.push_back(1);
}
else
{
for(int j=1;j<=val[i];j++)
va.push_back(0);
}
}
val.clear();
//val.shrink_to_fit();
cin>>s;
val.push_back(1);
goodB=1;
for(char c:s)
{
if(c=='1')
{
//multiply();
goodB*=2LL;
}
if(c=='2')
{
//multiply();
goodB*=2LL;
//add();
goodB++;
}
if(c=='U')
{
//divide();
goodB/=2;
}
if(c=='L')
{
//subtract();
goodB--;
}
if(c=='R')
{
//add();
goodB++;
}
}
for(int i=0;i<val.size();i++)
{
if(i%2==0)
{
for(int j=1;j<=val[i];j++)
vb.push_back(1);
}
else
{
for(int j=1;j<=val[i];j++)
vb.push_back(0);
}
}
ll rez=0;
ll ans=1e18;
/*while(va.size()>50)
{
va.pop_back();
rez++;
}
while(vb.size()>50)
{
vb.pop_back();
rez++;
}*/
assert(va.size()<=51);
ll a=0,b=0;
for(int i:va)
{
a=a*2LL+i;
//cout<<i;
}
/*for(int i:vb)
b=b*2LL+i;*/
assert(a==x);
//assert(a==goodA&&b==goodB);
a=goodA;
b=goodB;
if(a<b)
swap(a,b);
ll nivA=getniv(a),nivB=getniv(b);
while(nivA>nivB)
{
nivA--;
rez++;
a/=2;
}
while(nivA>=0)
{
ans=min(ans,rez+abs(a-b));
rez+=2;
a/=2;
b/=2;
nivA--;
}
cout<<ans;
return 0;
}
Compilation message
board.cpp: In function 'void divide()':
board.cpp:20:9: warning: unused variable 'last' [-Wunused-variable]
20 | int last=lg%2;
| ^~~~
board.cpp: In function 'int main()':
board.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i=0;i<val.size();i++)
| ~^~~~~~~~~~~
board.cpp:207:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0;i<val.size();i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
2572 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2536 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
2572 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
