QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725148#5117. Find MaximumYurily#AC ✓3ms3904kbC++202.4kb2024-11-08 16:27:272024-11-08 16:27:27

Judging History

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

  • [2024-11-08 16:27:27]
  • 评测
  • 测评结果：AC
  • 用时：3ms
  • 内存：3904kb
查看
  • [2024-11-08 16:27:27]
  • 提交

answer

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

typedef long long LL;
const int L = 39;

    LL tri[L + 3];
    LL l, r;

LL pick(LL x, int i){
    return x / tri[i] % 3;
}

bool check(LL x, int i){
    for(int j = i; j >= 0; j--)
        if(pick(x, j) != 2)
            return false;
    return true;
}

bool check1(LL x, int i){
    if(i < 0)
        return false;
    bool c1 = false;
    for(int j = i, xi; j >= 0; j--){
        xi = pick(x, j);
        if(xi == 0)
            return false;
        if(xi == 1)
            if(c1)
                return false;
            else{
                c1 = true;
                continue;
            }
    }
    return true;
}

void sol(){
    scanf("%lld%lld", &l, &r);

    int sum = 0;
    int flag = -1;
    for(int k = L, li, ri; k >= 0; k--){
        li = pick(l, k);
        ri = pick(r, k);

        if(flag == -1 && ri > 0){
            flag = k;
            sum += k + 1;
        }

        if(li == ri){
            if(flag != -1)
                sum += li;
            continue;
        }
        
        if(ri == 1){
            if(check(r, k - 1)){
                // printf("here1\n");
                printf("%d\n", sum + 1 + k * 2);        //[0..k-1]*2 => k * 2
                return ;
            }
            else {
                if(flag == k){
                    if(check1(r, k - 1))
                        printf("%d\n", sum + 1 + (k - 1) * 2 + 1);
                    else {
                        if(k > 0 && pick(r, k - 1) == 2)
                            printf("%d\n", sum + k * 2);
                        else
                            printf("%d\n", sum - 1 + k * 2);
                    }
                }
                else {
                    // printf("here3");
                    printf("%d\n", sum + 0 + k * 2);
                }
                return ;
            }
        }
        else {  //ri==2
            if(check(r, k - 1)){
                printf("%d\n", sum + 2 + k * 2);
                return ;
            }
            else {
                printf("%d\n", sum + 1 + k * 2);
                return ;
            }
        }
    }

    printf("%d\n", sum);
}

int main(){
    tri[0] = 1;
    for(int i = 1; i <= L; i++)
        tri[i] = tri[i - 1] * 3;

    int T;
    scanf("%d", &T);
    while(T--)
        sol();

    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

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: 0
Accepted
time: 0ms
memory: 3888kb

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:

ok 5050 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 3904kb

input:

10000
2924776299390853 348932224550662831
638290869233943020 897334616745111026
210780034220004669 279345354637770906
20574264013277469 387573622060864735
39441497975868873 806211034038773415
19845198891021950 243636832211738144
298454268109304380 988142879006387197
613847475002049291 86666797163210...

output:

110
112
109
110
112
108
113
112
110
107
109
113
110
111
111
111
109
108
111
113
111
111
113
112
111
110
111
108
111
110
111
111
112
111
113
109
111
110
108
111
111
113
110
110
110
112
110
107
111
111
109
107
112
111
110
111
112
111
111
112
111
111
109
111
110
111
112
111
113
110
113
112
112
110
110
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

144
3 8
2 8
2 9
3 9
9 26
8 26
8 27
9 27
27 80
26 80
26 81
27 81
81 242
80 242
80 243
81 243
243 728
242 728
242 729
243 729
729 2186
728 2186
728 2187
729 2187
2187 6560
2186 6560
2186 6561
2187 6561
6561 19682
6560 19682
6560 19683
6561 19683
19683 59048
19682 59048
19682 59049
19683 59049
59049 17...

output:

6
6
6
6
9
9
9
9
12
12
12
12
15
15
15
15
18
18
18
18
21
21
21
21
24
24
24
24
27
27
27
27
30
30
30
30
33
33
33
33
36
36
36
36
39
39
39
39
42
42
42
42
45
45
45
45
48
48
48
48
51
51
51
51
54
54
54
54
57
57
57
57
60
60
60
60
63
63
63
63
66
66
66
66
69
69
69
69
72
72
72
72
75
75
75
75
78
78
78
78
81
81
81...

result:

ok 144 numbers
English 繁體中文 简体中文

服务器时间: 2024-12-02 13:41:40 | 开源项目