Задачу предложил Әбдірахман Исмаил bash.
Нам нужно найти минимальное x, что x * k > n. Легко видеть, что . Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая этим функциям и их свойствам.
Решение на С++li n, k;
bool read() {
return !!(cin >> n >> k);
}
void solve() {
cout << (n / k + 1) * k << endl;
}
Сложность: O(1).
Задачу предложил Артур Яворски KingArthur.
Два календаря совпадают если и только, если в них одинаковое количество дней и они начинаются с одного дня недели. Таким образом, достаточно было просто перебрать следующий год, поддерживая первый день недели в году. На самом деле день недели каждый год увеличивается на единицу. Исключением являются високосные годы, когда день недели увеличивается на два.
Решение на C++int 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;
}
Сложность: O(1) — легко видеть, что количество итерация не превосходит небольшой константы.
Задачу предложил Sheikh Monir skmonir.
Легко видеть, что в оба цвета мы можем покрасить доски с номерами кратными lcm(a, b) — НОК чисел a и b. Очевидно, что эти доски выгоднее красить в более дорогой цвет. Таким образом, ответ равен: .
Решение на C++li 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;
}
Сложность: O(log(max(a, b))).
Задачу предложил Zi Song Yeoh zscoder.
В этой задаче можно было вывести формулу в качестве ответа: для этого нужно было посчитать сумму геометрической прогрессии. Далее формулу было легко посчитать с помощью бинарного возведения в степень.
Я опишу более сложное, но более общее решение. Если у нас есть некоторый набор переменных, который пошагово пересчитывается друг через друга с помощью линейной функции, то можно применить бинарное возведение в степень матрицы. Итак, в нашей задаче переменная была одна x. Новая переменная x' получалась по формуле A·x + B. Рассмотрим матрицу z = [[A, B], [0, 1]] и вектор v = [x, 1]. Умножим z на v слева. Легко видеть, что получится вектор v' = [x', 1]. Таким образом, чтобы сделать n итераций, мы просто должны n раз умножить слева матрицу z на вектор v. В силу свойства ассоциативности операции умножения матриц перемножение мы можем сделать бинарно.
В качестве упражнения можете попробовать выписать самостоятельно матрицу для чисел Фиббоначи и научиться их быстро считать. Под спойлером матрица и вектор.
Матрица и вектор для чисел Фиббоначиz=[[0, 1], [1, 1]], v=[0, 1].
Решение на C++int 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;
}
Сложность: O(logn).
Задачу предложил и подготовил Алексей Дергунов dalex.
Давайте решать задачу динамикой. zmask, i — наибольшая вероятность выиграть Ивану, если джедаи из маски mask уже хоть раз сражались, а в живых остался только i-й джедай. Для подсчёта динамики переберём следующего джедая (ему придётся сражаться против i-го джедая): .
Решение на C++const 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;
}
Сложность по времени: O(2nn2).
Сложность по памяти: O(2nn).
Задачу предложил AmirMohammad Dehghan PrinceOfPersia.
Посмотрим на задачу геометрически: пары чисел в множестве это просто прямые, задача по вертикальной прямой найти самое верхнее её пересечение с какой-либо прямой.
Разобьём все запросы на блоков. Рассмотрим те прямые, которые были добавлены до начала блока и не будут удалены в нём. Построим по этому множеству нижнее огибающее множество. Теперь, чтобы ответить на один запрос третьего типа нужно взять максимум по прямым нижнего огибающего множества и по запросам в блоке до текущего запроса. Последних не более , поэтому по ним мы можем пройти в лоб и обновить ответ. Теперь посмотрим на все запросы в блоке третьего типа, отсортируем их слева направо и будет искать оптимальную прямую в огибающем множестве с помощью двух указателей.
Решение на C++const 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");
}
}
}
}
Сложность: .