QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65112#5117. Find Maximumdad11WA 8ms3472kbC++143.3kb2022-11-27 16:52:592022-11-27 16:53:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-27 16:53:00]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3472kb
  • [2022-11-27 16:52:59]
  • 提交

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'