#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
/*
p[0] > p[1] > ... > p[n-1]
ST 1:
*) p[0] > p[1]
*) Make transaction p[0]-1
-> Then buying exactly one of type 1
ST 4:
*) p[0] > p[1] > p[2]
*) T1: M=p[0]-1
--> Case 1: Buying only one souvenir
- Bought p[1]
- C := M-p[1] <--> p[1] = M-C
- T2: p[1]-1
--> Case 2: Bought 2 souvenirs
M=100,
C=11
(M-C)/2 - 1
100 coins, get back 11
-> 2 souvenirs are 89
- p[1] > p[2]
- p[1] + p[2] = 89
- 89 > 2*p[2]
- 44 > p[2]
p[2] <= 43
*/
void buy_souvenirs(int N, long long P0) {
if (N == 2) {
transaction(P0-1);
} else if (N == 3) {
long long M = P0-1;
auto r = transaction(M);
long long C = r.second;
if (r.first.size() == 1) {
transaction(M-C-1);
} else {
transaction((M-C)/2-1);
}
} else {
// Subtask 2
for (int j = 1; j <= N-1; ++j) {
for (int i = j; i <= N-1; ++i) {
transaction(N-i);
}
}
}
}
#ifdef LOCAL
int32_t main() {
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |