QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #139459 | #5259. Skills in Pills | tselmegkh# | WA | 98ms | 24008kb | C++20 | 3.2kb | 2023-08-13 16:49:05 | 2023-08-13 16:49:07 |
Judging History
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) / i + (n - lst) / j;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
5 5 5
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
3 8 11
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
5 8 16
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
9 7 279
output:
70
result:
ok single line: '70'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
8 3 56
output:
25
result:
ok single line: '25'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
5 9 46
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
8 4 251
output:
93
result:
ok single line: '93'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
8 7 41
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
60 17 360
output:
27
result:
ok single line: '27'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
16 55 388
output:
31
result:
ok single line: '31'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
25 38 292
output:
18
result:
ok single line: '18'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
22 59 177
output:
11
result:
ok single line: '11'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
4 3 82
output:
50
result:
ok single line: '50'
Test #21:
score: 0
Accepted
time: 52ms
memory: 11432kb
input:
77 18 511543
output:
35070
result:
ok single line: '35070'
Test #22:
score: 0
Accepted
time: 98ms
memory: 19004kb
input:
37 32 987861
output:
57612
result:
ok single line: '57612'
Test #23:
score: 0
Accepted
time: 5ms
memory: 8232kb
input:
29 8 300899
output:
48059
result:
ok single line: '48059'
Test #24:
score: 0
Accepted
time: 5ms
memory: 11400kb
input:
73 83 533839
output:
13745
result:
ok single line: '13745'
Test #25:
score: 0
Accepted
time: 8ms
memory: 6928kb
input:
12 23 181193
output:
23008
result:
ok single line: '23008'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 2 864514
output:
864514
result:
ok single line: '864514'
Test #27:
score: 0
Accepted
time: 16ms
memory: 6204kb
input:
27 7 165249
output:
29765
result:
ok single line: '29765'
Test #28:
score: 0
Accepted
time: 24ms
memory: 18540kb
input:
15 2 751665
output:
429522
result:
ok single line: '429522'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3436kb
input:
2 16 818146
output:
460207
result:
ok single line: '460207'
Test #30:
score: 0
Accepted
time: 13ms
memory: 13004kb
input:
43 88 631366
output:
21860
result:
ok single line: '21860'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
215 1222 3597
output:
18
result:
ok single line: '18'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
9619 3375 604892
output:
241
result:
ok single line: '241'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
861 1924 311511
output:
522
result:
ok single line: '522'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3440kb
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: 3456kb
input:
6273 7732 122377
output:
34
result:
ok single line: '34'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
8057 7746 89137
output:
22
result:
ok single line: '22'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
9215 8952 74618
output:
16
result:
ok single line: '16'
Test #39:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
7246 3709 129579
output:
51
result:
ok single line: '51'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
4052 6785 831888
output:
327
result:
ok single line: '327'
Test #41:
score: 0
Accepted
time: 2ms
memory: 5704kb
input:
9 2 91067
output:
56916
result:
ok single line: '56916'
Test #42:
score: 0
Accepted
time: 22ms
memory: 24008kb
input:
10 3 913595
output:
406041
result:
ok single line: '406041'
Test #43:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
2 2 152575
output:
152575
result:
ok single line: '152575'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
2 2 927771
output:
927771
result:
ok single line: '927771'
Test #45:
score: 0
Accepted
time: 25ms
memory: 14420kb
input:
6 7 637014
output:
200204
result:
ok single line: '200204'
Test #46:
score: 0
Accepted
time: 7ms
memory: 19740kb
input:
5 3 721417
output:
400786
result:
ok single line: '400786'
Test #47:
score: -100
Wrong Answer
time: 9ms
memory: 7744kb
input:
5 9 183079
output:
57539
result:
wrong answer 1st lines differ - expected: '57538', found: '57539'