QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168993#5117. Find MaximumarahatoWA 9ms3836kbC++141.2kb2023-09-09 10:20:452023-09-09 10:20:45

Judging History

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

  • [2023-09-09 10:20:45]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3836kb
  • [2023-09-09 10:20:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> san(int x){
	vector<int> a;
	while(x){
		a.push_back(x%3);
		x/=3;
	}
	return a;
}
/*
100
200
010
110
210
020
120
220
001
101
201
011
111
211
*/
void doit(int T){
	int l,r;
	cin>>l>>r;
	if(T==776) cout<<l<<" "<<r<<endl;
	vector<int> a=san(l),b=san(r);
	int n=b.size(),ans=n;
	while(a.size()<n) a.push_back(0);
	while(n&&a[n-1]==b[n-1]) ans+=a[n-1],n--,b.pop_back();
	if(!n){
		cout<<ans<<endl;
		return ;
	}
	ans+=(n-1)*2+b[n-1]-1;
	bool fl=1;
	for(int i=0;i<n-1;i++) fl&=b[i]==2;
	if(!fl&&b.back()==1){
		int t=ans+1;
		if(n>1){
			bool fll=0;
			for(int i=n-2;i>=0;i--) if(b[i]){
				fll=1;
				for(int j=0;j<i;j++) fll&=b[j]==2;
				if(fll){
					if(b[i]==1) t--;
					break;
				}
				if(b[i]==1){
					if(i==0) t--;
					else t-=2;
				}
				if(b[i]==2){
					if(i) t--;
				}
				fll=1;
				break;
			}
			else t-=2;
//			if(!fll){
//				t-=(n-1)*2;
//			}
		}
		cout<<max(ans-1+fl,t)<<endl;
		return ;
	}
	cout<<ans+fl<<endl;
}

signed main(){
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	for(int i=1;i<=t;i++) doit(i);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3836kb

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: 9ms
memory: 3624kb

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 776th numbers differ - expected: '6', found: '9'