QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65171#5117. Find MaximumJWChen#AC ✓8ms3668kbC++143.6kb2022-11-27 21:54:112022-11-27 21:54:12

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 21:54:12]
  • 评测
  • 测评结果：AC
  • 用时：8ms
  • 内存：3668kb
查看
  • [2022-11-27 21:54:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T;
ll l,r,a[1001],b[1001],sa,sb,ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&l,&r);
        ll tmp;
        sa=0;
        sb=0;
        ans=0;
        tmp=l;
        while(tmp)
        {
            sa++;
            a[sa]=tmp%3;
            tmp/=3;
        }
        tmp=r;
        while(tmp)
        {
            sb++;
            b[sb]=tmp%3;
            tmp/=3;
        }
    //    printf("sa=%lld sb=%lld\n",sa,sb);
        if(sa==sb)//sa<=sb
        {
            ans=sa;
            ll wz=-1,tmpa=0;
            for(int i=sa;i>=1;--i)
                if(a[i]!=b[i])
                {
                    wz=i;
                    break;
                }
                else ans+=a[i];
            //l<=r a[wz]<b[wz]
            if(wz==-1) tmpa=0;
            else if(b[wz]==2) 
            {
                bool f=true;
                for(int i=wz;i>=1;--i)
                    if(b[i]!=2)
                    {
                        f=false;
                        break;
                    }
                if(f) tmpa=(wz-1)*2+2;
                else tmpa=(wz-1)*2+1;
            }
            else if(b[wz]==1)
            {
                bool f=true;
                for(int i=wz-1;i>=1;--i)
                    if(b[i]!=2)
                    {
                        f=false;
                        break;
                    }
                if(f) tmpa=(wz-1)*2+1;
                else tmpa=(wz-1)*2+0;
            }
            ans+=tmpa;
        }
        else if(sa<sb)
        {
            ll tmpa,tmpaa,wz;
            tmpa=0;
            tmpaa=sb;
            wz=-1;
            for(int i=sb;i>=1;i--)
                if(b[i]!=2)
                {
                    wz=i;
                    break;
                }
            if(wz==-1)
            {
                tmpaa+=2*sb;
            }
            else if(wz!=sb) 
            {
                tmpaa+=wz*2+1+(sb-wz-1)*2;
            //    printf("wz=%lld tmpaa=%lld\n",wz,tmpaa);
            }
            else//最高位是1
            {
                tmpaa+=b[sb];
                wz=-1;
                for(int i=sb-1;i>=1;i--)
                    if(b[i]!=0)
                    {
                        wz=i;
                        break;
                    }
                if(wz!=-1)
                {
                    if(b[wz]==1)
                    {
                        bool f=true;
                        for(int i=wz-1;i>=1;--i)
                            if(b[i]!=2)
                            {
                                f=false;
                                break;
                            }
                        if(f) tmpaa+=1+2*(wz-1);
                        else tmpaa+=0+2*(wz-1);
                    }
                    else if(b[wz]==2)
                    {
                        bool f=true;
                        for(int i=wz-1;i>=1;--i)
                            if(b[i]!=2)
                            {
                                f=false;
                                break;
                            }
                        if(f) tmpaa+=2+2*(wz-1);
                        else tmpaa+=1+2*(wz-1);
                    }
                }
            }
            tmpa=max(tmpa,tmpaa);
            tmpaa=sb-1+2*(sb-1);    
            tmpa=max(tmpa,tmpaa);
            ans=tmpa;
        }
        printf("%lld\n",ans);
    }
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3520kb

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: 2ms
memory: 3668kb

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: 8ms
memory: 3472kb

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: 3564kb

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 繁體中文 简体中文

Server Time: 2024-12-02 13:34:06 | OpenSource Project