QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65112 | #5117. Find Maximum | dad11 | WA | 8ms | 3472kb | C++14 | 3.3kb | 2022-11-27 16:52:59 | 2022-11-27 16:53:00 |
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()
{
int t;
cin>>t;
while(t--)
{
LL l,r;
cin>>l>>r;
if(r<=3)
{
cout<<f(r)<<endl;
continue;
}
vector<int> a,b;
while(l)
{
a.push_back(l%3);
l/=3;
}
while(r)
{
b.push_back(r%3);
r/=3;
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
if(a.size()==b.size())
{
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;
continue;
}
int pos=0;
int sum=0;
for(int i=0;i<b.size();i++)
{
if(b[i]!=a[i]&&b[i]!=0)
{
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();
}
else
{
for(int i=0;i<b.size();i++) sum+=b[i];
sum+=b.size();
}
cout<<sum<<endl;
}
else if(b.size()==a.size()+1)
{
// 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());
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;
continue;
}
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];
sum=2;
sum+=(b.size()-2)*2+b.size();
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;
}
}
}
else
{
//cout<<"Yes"<<endl;
int cnt=0;
for(int i=1;i<b.size();i++) cnt+=b[i];
if(cnt==2*(b.size()-1))
{
//cout<<"1"<<endl;
cnt+=b[0];
cnt+=b.size();
cout<<cnt<<endl;
continue;
}
if(b[0]==1)
{
if(b[1]==2)
{
cnt-=b[1];
if(2*(b.size()-2)-cnt>=2)
{
cnt=2*(b.size()-2);
cnt+=2;
cnt+=b.size();
}
else
{
cnt+=b[0]+b[1];
cnt+=b.size();
}
}
else if(b[1]==1)
{
if(2*(b.size()-1)-cnt>2)
{
cnt=3*(b.size()-1);
}
else
{
cnt+=b[0];
cnt+=b.size();
}
}
else//b[1]=0;
{
cnt=3*(b.size()-1);
}
}
else if(b[0]==2)
{
//cout<<"4"<<endl;
cnt=2*(b.size()-1)+1+b.size();
}
cout<<cnt<<endl;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 3388kb
input:
10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
3 3 4 5 3 4 5 4 5 5
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 3472kb
input:
5050 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
2 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 3 3 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8...
result:
wrong answer 491st numbers differ - expected: '4', found: '5'