QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#65080 | #5117. Find Maximum | Tntac7 | WA | 3ms | 3412kb | C++14 | 2.9kb | 2022-11-27 15:20:36 | 2022-11-27 15:20:39 |
Judging History
answer
//题目:f[x]= 1 x=0
// f[x/3]+1 xmod3=0
// f[x-1]+1 xmod3!=0
//给定一个区间,问该区间了f的最大值
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include<vector>
using namespace std;
typedef long long LL;
const int N=40;
int f(int x)
{
if(x==2) return 3;
if(x==1) return 2;
if(x==0) return 1;
if(x==3) return 3;
}
int main()
{
LL l,r;
cin>>l>>r;
if(r<=3)
{
cout<<f(r)<<endl;
return 0;
}
vector<int> a,b;
while(l)
{
a.push_back(l%3);
l/=3;
}
while(r)
{
b.push_back(r%3);
r/=3;
}
if(a.size()==b.size())
{
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int cnt=0;
for(int i=1;i<b.size();i++) cnt+=b[i];
if(cnt==2*(b.size()-1))
{
cnt+=b[0];
cnt+=b.size();
cout<<cnt<<endl;
return 0;
}
int pos=0;
int sum=0;
for(int i=0;i<b.size();i++)
{
if(b[i]!=a[i])
{
pos=i;
break;
}
}
bool flag=true;
for(int i=pos+1;i<b.size();i++)
{
if(b[i]!=2)
{
flag=false;
break;
}
}
if(flag==false)
{
b[pos]-=1;
for(int i=pos+1;i<b.size();i++) b[i]=2;
for(int i=0;i<b.size();i++) sum+=b[i];
sum+=b.size();
if(pos==0&&b[pos]==0) sum-=1;
}
else
{
for(int i=0;i<b.size();i++) sum+=b[i];
sum+=b.size();
}
cout<<sum<<endl;
}
else
{
int len=a.size();
for(int i=len;i<b.size();i++) a.push_back(0);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
// for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
// cout<<endl;
// for(int i=0;i<b.size();i++) cout<<b[i]<<" ";
// cout<<endl;
int cnt=0;
for(int i=1;i<b.size();i++) cnt+=b[i];
if(cnt==2*(b.size()-1))
{
cnt+=b[0];
cnt+=b.size();
cout<<cnt<<endl;
return 0;
}
if(b[0]==2)
{
int sum=2*(b.size()-1);
sum+=1;
sum+=b.size();
cout<<sum<<endl;
}
else if(b[0]==1)
{
if(b[1]==0)
{
int sum=2*(b.size()-1);
sum+=b.size()-1;
cout<<sum<<endl;
}
else if(b[1]==2)
{
int sum=0;
for(int i=2;i<b.size();i++) sum+=b[i];
if(a[1]<=2)
{
sum=2;
sum+=2*(b.size()-2);
sum+=b.size();
}
// else//a[1]==2
// {
// if(2*(b.size()-2)-sum<=2)
// {
// sum+=3;
// sum+b.size();
// }
// else
// {
// sum=2*(b.size()-1);
// sum+=b.size()-1;
// }
// }
cout<<sum<<endl;
}
else if(b[1]==1)
{
int sum=0;
for(int i=2;i<b.size();i++) sum+=b[i];
if(2*(b.size()-2)==sum)
{
sum+=2;
sum+=b.size();
}
else
{
sum=2*(b.size()-1);
sum+=b.size()-1;
}
cout<<sum<<endl;
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3412kb
input:
10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'