QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142525#5259. Skills in PillstselmegkhAC ✓103ms24056kbC++203.2kb2023-08-19 10:30:482023-08-19 10:30:50

Judging History

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

  • [2023-08-19 10:30:50]
  • 评测
  • 测评结果：AC
  • 用时：103ms
  • 内存：24056kb
查看
  • [2023-08-19 10:30:48]
  • 提交

answer

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <queue>
    #include <stack>
    #include <cstdlib>
    #include <cmath>
    #include <cstring>
    #include <iomanip>
    using namespace std;

    const int N = 2e5 + 5, inf = 1e9;
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define ff first
    #define ss second
    #define all(a) a.begin(),a.end()
    #define sz(x) (int)x.size()
    typedef vector<int> vi;
    typedef pair<int,int> ii;
    typedef vector<ii> vii;

    ll dp[1000006][2];
    ll n, i, j;
    ll doit(ll lst, ll type){
        if(dp[lst][type] != 0) return dp[lst][type];
        if(type == 1 && lst + i - 1 > n && lst + j > n) return 0;
        if(type == 0 && lst + j - 1 > n && lst + i > n) return 0;
        if(type == 1){
            // i, j
            ll cnt = 0;
            while(true){
                cnt += 1LL * j;
                if((cnt + 1) % i == 0) break;
            }
            if(1LL * lst + cnt > 1LL * n){
                dp[lst][type] = (n - lst + 1) / i + (n - lst) / j;
                return dp[lst][type];
            }
            else{
                dp[lst][type] = ((cnt + 1 ) / i + cnt / j) + min(doit(lst + cnt, 0), doit(lst + cnt, 1));
                return dp[lst][type];
            }
        }
        else{
            //  j i 
            ll cnt = 0;
            while(true){
                cnt += 1LL * i;

                if((cnt + 1) % j == 0) break;
            }
            if(1LL * cnt + lst > 1LL * n){
                dp[lst][type] = (n - lst + 1) / j + (n - lst) / i;
                return dp[lst][type];
            }
            else{
                dp[lst][type] = ((cnt + 1 ) / j + cnt / i) + min(doit(lst + cnt, 0), doit(lst + cnt, 1));
                return dp[lst][type];
            }
        }
        return dp[lst][type];
    }


    void solve(){
        cin >> i >> j >> n;
        
        if(i == j){
            if(n % i == 0){
                cout << (n / i) * 2 << '\n';
            }   
            else{
                if(n % i + 1 >= i){
                cout << (n / i) * 2 + 1 << '\n';
                }
                else cout << (n / i) * 2 << '\n';
            }
            return;
        }
        long long lst = 0;

        while(true){
            lst += 1LL * i;
            if(lst % j == 0){
                break;
            }
        }

        ll ans = 0;
        if(lst >= 1LL * n){
            ans = n / i + n / j;
            cout << ans << '\n';
            return;
        }
        else{
            if(__gcd(i, j) != 1){
                ans = 1LL * min((n - lst) / i + (n - lst + 1) / j, (n - lst + 1) / i + (n - lst) / j) + lst / i + lst / j;
                cout << ans << '\n';
                return;
            }
            ans = 1LL * min(doit(lst, 1), doit(lst, 0)) + lst / i + lst / j;
            cout << ans << '\n';
            return;
        }
        return;
    }

    int main(){
        int t = 1;
        while(t--){
            solve();
        }
        return 0;
    }
源文件, 语言: C++20

詳細信息

Test #1:

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

input:

3 9 20

output:

8

result:

ok single line: '8'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

8 2 12

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

2 5 15

output:

10

result:

ok single line: '10'

Test #4:

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

input:

10 8 13

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

6 6 19

output:

6

result:

ok single line: '6'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

2 3 5

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

4 2 8

output:

6

result:

ok single line: '6'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

5 5 5

output:

2

result:

ok single line: '2'

Test #9:

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

input:

3 8 11

output:

4

result:

ok single line: '4'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

5 8 16

output:

5

result:

ok single line: '5'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

9 7 279

output:

70

result:

ok single line: '70'

Test #12:

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

input:

8 3 56

output:

25

result:

ok single line: '25'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

5 9 46

output:

14

result:

ok single line: '14'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3332kb

input:

8 4 251

output:

93

result:

ok single line: '93'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

8 7 41

output:

10

result:

ok single line: '10'

Test #16:

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

input:

60 17 360

output:

27

result:

ok single line: '27'

Test #17:

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

input:

16 55 388

output:

31

result:

ok single line: '31'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3336kb

input:

25 38 292

output:

18

result:

ok single line: '18'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

22 59 177

output:

11

result:

ok single line: '11'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3332kb

input:

4 3 82

output:

50

result:

ok single line: '50'

Test #21:

score: 0
Accepted
time: 50ms
memory: 11484kb

input:

77 18 511543

output:

35070

result:

ok single line: '35070'

Test #22:

score: 0
Accepted
time: 103ms
memory: 19004kb

input:

37 32 987861

output:

57612

result:

ok single line: '57612'

Test #23:

score: 0
Accepted
time: 6ms
memory: 8268kb

input:

29 8 300899

output:

48059

result:

ok single line: '48059'

Test #24:

score: 0
Accepted
time: 5ms
memory: 11292kb

input:

73 83 533839

output:

13745

result:

ok single line: '13745'

Test #25:

score: 0
Accepted
time: 12ms
memory: 6892kb

input:

12 23 181193

output:

23008

result:

ok single line: '23008'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

2 2 864514

output:

864514

result:

ok single line: '864514'

Test #27:

score: 0
Accepted
time: 12ms
memory: 6160kb

input:

27 7 165249

output:

29765

result:

ok single line: '29765'

Test #28:

score: 0
Accepted
time: 27ms
memory: 18608kb

input:

15 2 751665

output:

429522

result:

ok single line: '429522'

Test #29:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

2 16 818146

output:

460207

result:

ok single line: '460207'

Test #30:

score: 0
Accepted
time: 13ms
memory: 13040kb

input:

43 88 631366

output:

21860

result:

ok single line: '21860'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

215 1222 3597

output:

18

result:

ok single line: '18'

Test #32:

score: 0
Accepted
time: 1ms
memory: 3332kb

input:

9619 3375 604892

output:

241

result:

ok single line: '241'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

861 1924 311511

output:

522

result:

ok single line: '522'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3392kb

input:

9249 3782 866972

output:

322

result:

ok single line: '322'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

7055 8386 206874

output:

53

result:

ok single line: '53'

Test #36:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

6273 7732 122377

output:

34

result:

ok single line: '34'

Test #37:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

8057 7746 89137

output:

22

result:

ok single line: '22'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

9215 8952 74618

output:

16

result:

ok single line: '16'

Test #39:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

7246 3709 129579

output:

51

result:

ok single line: '51'

Test #40:

score: 0
Accepted
time: 1ms
memory: 3332kb

input:

4052 6785 831888

output:

327

result:

ok single line: '327'

Test #41:

score: 0
Accepted
time: 1ms
memory: 5640kb

input:

9 2 91067

output:

56916

result:

ok single line: '56916'

Test #42:

score: 0
Accepted
time: 20ms
memory: 24056kb

input:

10 3 913595

output:

406041

result:

ok single line: '406041'

Test #43:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

2 2 152575

output:

152575

result:

ok single line: '152575'

Test #44:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

2 2 927771

output:

927771

result:

ok single line: '927771'

Test #45:

score: 0
Accepted
time: 18ms
memory: 14480kb

input:

6 7 637014

output:

200204

result:

ok single line: '200204'

Test #46:

score: 0
Accepted
time: 15ms
memory: 19744kb

input:

5 3 721417

output:

400786

result:

ok single line: '400786'

Test #47:

score: 0
Accepted
time: 9ms
memory: 7576kb

input:

5 9 183079

output:

57538

result:

ok single line: '57538'

Test #48:

score: 0
Accepted
time: 10ms
memory: 17016kb

input:

9 2 579290

output:

362055

result:

ok single line: '362055'

Test #49:

score: 0
Accepted
time: 12ms
memory: 16276kb

input:

3 4 546909

output:

341817

result:

ok single line: '341817'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3440kb

input:

2 2 932611

output:

932611

result:

ok single line: '932611'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 17:04:14 | 開源專案