The problem was suggested by Abdrakhman Ismail bash.
We should find minimal x, so x·k > n. Easy to see that . To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik "Concrete Mathematics". There is a chapter there about that functions and their properties.
С++ solutionli n, k;
bool read() {
return !!(cin >> n >> k);
}
void solve() {
cout << (n / k + 1) * k << endl;
}
Complexity: O(1).
The problem was suggested by Arthur Jaworski KingArthur.
Two calendars are same if and only if they have the same number of days and starts with the same day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st (for example). Easy to see that the day of a week increases by one each year except of the leap years, when it increases by two.
C++ solutionint y;
bool read() {
return !!(cin >> y);
}
bool leap(int y) {
return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
void solve() {
bool is_leap = leap(y);
int d = 0;
do {
d++;
if (leap(y)) d++;
y++;
d %= 7;
} while (d || leap(y) != is_leap);
cout << y << endl;
}
Complexity: O(1) — easy to see that we will not iterate more than some small fixed constant times.
The problem was suggested by Sheikh Monir skmonir.
Easy to see that we can paint with both colours only tiles with the numbers multiple of lcm(a, b). Obviously that tiles should be painted with more expensive colour. So the answer equals to .
C++ solutionli n, a, b, p, q;
bool read() {
return !!(cin >> n >> a >> b >> p >> q);
}
li gcd(li a, li b) { return !a ? b : gcd(b % a, a); }
li lcm(li a, li b) { return a / gcd(a, b) * b; }
void solve() {
li ans = 0;
ans += (n / a) * p;
ans += (n / b) * q;
ans -= (n / lcm(a, b)) * min(p, q);
cout << ans << endl;
}
Complexity: O(log(max(a, b))).
The problem was suggested by Zi Song Yeoh zscoder.
The problem can be solved using closed formula: it's need to calculate the sum of geometric progression. The formula can be calculated using binary exponentiation.
I'll describe more complicated solution, but it's more general. If we have a set of variables and at each step all variables are recalculating from each other using linear function, we can use binary matrix exponentiation. There is only one variable x in our problem. The new variable x' is calculating using formula A·x + B. Consider the matrix z = [[A, B], [0, 1]] and the vector v = [0, 1]. Let's multiply z and v. Easy to see that we will get the vector v' = [x', 1]. So to make n iterations we should multiply z and v n times. We can do that using binary matrix exponentiation, because matrix multiplication is associative.
As an exercise try to write down the matrix for the Fibonacci numbers and calculate the n-th Fibonacci number in O(logn) time. The matrix and the vector is under the spoiler.
The matrix and the vector for the Fibonacci numbersz=[[0, 1], [1, 1]], v=[0, 1].
C++ solutionint A, B, x;
li n;
bool read() {
return !!(cin >> A >> B >> n >> x);
}
const int mod = 1000 * 1000 * 1000 + 7;
inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
inline void inc(int& a, int b) { a = add(a, b); }
void mul(int a[2][2], int b[2][2]) {
static int res[2][2];
forn(i, 2)
forn(j, 2) {
res[i][j] = 0;
forn(k, 2) inc(res[i][j], mul(a[i][k], b[k][j]));
}
forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
}
void bin_pow(int a[2][2], li b) {
static int res[2][2];
forn(i, 2) forn(j, 2) res[i][j] = i == j;
while (b) {
if (b & 1) mul(res, a);
mul(a, a);
b >>= 1;
}
forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
}
void solve() {
int z[2][2] = {
{ A, B },
{ 0, 1 }
};
bin_pow(z, n);
int result = add(mul(z[0][0], x), z[0][1]);
cout << result << endl;
}
Complexity: O(logn).
The problem was suggested and prepared by Alexey Dergunov dalex.
Let's solve the problem using dynamic programming. zmask, i — the maximal probability of Ivans victory if the siths from the mask already fought and the i-th sith left alive. To calculate that DP we should iterate over the next sith (he will fight against the i-th sith): .
C++ solutionconst int N = 20, EXPN = (1 << 18) + 3;
int n;
ld p[N][N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) forn(j, n) assert(cin >> p[i][j]);
return true;
}
ld z[EXPN][N];
ld solve(int mask, int i) {
ld& ans = z[mask][i];
if (ans > -0.5) return ans;
if (mask == (1 << n) - 1) return ans = !i;
ans = 0;
forn(j, n)
if (!(mask & (1 << j))) {
ld cur = 0;
cur += solve(mask | (1 << j), i) * p[i][j];
cur += solve(mask | (1 << j), j) * p[j][i];
ans = max(ans, cur);
}
return ans;
}
void solve() {
if (n == 1) {
puts("1");
return;
}
forn(i, 1 << n) forn(j, n) z[i][j] = -1;
ld ans = 0;
forn(i, n)
forn(j, i) {
int mask = (1 << i) | (1 << j);
ld cur = 0;
cur += solve(mask, i) * p[i][j];
cur += solve(mask, j) * p[j][i];
ans = max(ans, cur);
}
cout << ans << endl;
}
Time complexity: O(2nn2).
Memory complexity: O(2nn).
The problem was suggested by AmirMohammad Dehghan PrinceOfPersia.
Let's interpret the problem geometrically: the pairs from the set are the lines and the problem to find to topmost intersection of the vertical line with the lines from the set.
Let's split the queries to blocks. Consider the lines added before the current block and that will not deleted in the current block. Let's build the lower envelope by that lines. Now to calculate the answer to the query we should get maximum over the lines from the envelope and the lines from the block before the current query that is not deleted yet. There are no more than lines from the block, so we can iterate over them. Let's find the answers from the envelope for all queries of the third type from the block at once: we should sort them and iterate over envelope using two pointers technique.
C++ solutionconst int N = 300300;
int n;
int t[N], a[N], b[N], id[N], q[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) {
assert(scanf("%d", &t[i]) == 1);
if (t[i] == 1) {
assert(scanf("%d%d", &a[i], &b[i]) == 2);
} else if (t[i] == 2) {
assert(scanf("%d", &id[i]) == 1);
id[i]--;
} else if (t[i] == 3) {
assert(scanf("%d", &q[i]) == 1);
} else throw;
}
return true;
}
bool in_set[N], deleted[N];
vector<pair<pti, int>> lines;
vector<pti> envelope;
void build_envelope() {
envelope.clear();
envelope.reserve(n);
forn(ii, sz(lines)) {
int i = lines[ii].y;
if (in_set[i] && !deleted[i]) {
assert(t[i] == 1);
pti c(a[i], b[i]);
while (!envelope.empty()) {
pti b = envelope.back();
if (b.x == c.x) {
envelope.pop_back();
continue;
} else if (sz(envelope) > 1) {
pti a = envelope[sz(envelope) - 2];
ld xc = ld(c.y - a.y) / (a.x - c.x);
ld xb = ld(b.y - a.y) / (a.x - b.x);
if (xc < xb) {
envelope.pop_back();
continue;
}
}
break;
}
envelope.pb(c);
}
}
}
li ans[N];
vector<pti> qs;
void process_qs() {
sort(all(qs));
int p = 0;
forn(i, sz(qs)) {
li q = qs[i].x;
int id = qs[i].y;
while (p + 1 < sz(envelope)) {
li cval = envelope[p].x * q + envelope[p].y;
li nval = envelope[p + 1].x * q + envelope[p + 1].y;
if (cval > nval) break;
p++;
}
if (p < sz(envelope)) {
ans[id] = envelope[p].x * q + envelope[p].y;
}
}
}
void solve() {
lines.clear();
lines.reserve(n);
forn(i, n) if (t[i] == 1) lines.pb(mp(mp(a[i], b[i]), i));
sort(all(lines));
memset(in_set, false, sizeof(in_set));
memset(deleted, false, sizeof(deleted));
forn(i, n) ans[i] = LLONG_MIN;
int blen = int(sqrtl(n));
blen = 2500;
for (int l = 0; l < n; l += blen) {
int r = min(n, l + blen);
memset(deleted, false, sizeof(deleted));
fore(i, l, r) if (t[i] == 2) deleted[id[i]] = true;
build_envelope();
qs.clear();
qs.reserve(r - l);
fore(i, l, r) if (t[i] == 3) qs.pb(mp(q[i], i));
process_qs();
fore(i, l, r) {
if (t[i] == 1) in_set[i] = true;
else if (t[i] == 2) in_set[id[i]] = false;
else {
fore(j, l, r) {
if (t[j] == 1 && in_set[j])
ans[i] = max(ans[i], li(a[j]) * q[i] + b[j]);
else if (t[j] == 2 && in_set[id[j]])
ans[i] = max(ans[i], li(a[id[j]]) * q[i] + b[id[j]]);
}
if (ans[i] != LLONG_MIN) printf("%lldn", ans[i]);
else puts("EMPTY SET");
}
}
}
}
Complexity: .