678A - Вася любит числа

Задачу предложил Әбдірахман Исмаил bash.

Нам нужно найти минимальное x, что x * k > n. Легко видеть, что . Для подробного знакомства с математическими функциями пола и потолка я рекомендую книгу авторов Грэхем, Кнут, Паташник "Конкретная математика". В этой книге есть отдельная глава, посвящённая этим функциям и их свойствам.

li n, k;

bool read() {
	return !!(cin >> n >> k);
}

void solve() {
	cout << (n / k + 1) * k << endl;
}

Сложность: O(1).

678B - Такой же календарь

Задачу предложил Артур Яворски KingArthur.

Два календаря совпадают если и только, если в них одинаковое количество дней и они начинаются с одного дня недели. Таким образом, достаточно было просто перебрать следующий год, поддерживая первый день недели в году. На самом деле день недели каждый год увеличивается на единицу. Исключением являются високосные годы, когда день недели увеличивается на два.

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) — легко видеть, что количество итерация не превосходит небольшой константы.

678C - Мила и шоколад

Задачу предложил Sheikh Monir skmonir.

Легко видеть, что в оба цвета мы можем покрасить доски с номерами кратными lcm(a, b) — НОК чисел a и b. Очевидно, что эти доски выгоднее красить в более дорогой цвет. Таким образом, ответ равен: .

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(logmax(a, b)).

678D - Итерированная линейная функция

Задачу предложил 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. В силу свойства ассоциативности операции умножения матриц перемножение мы можем сделать бинарно.

В качестве упражнения можете попробовать выписать самостоятельно матрицу для чисел Фиббоначи и научиться их быстро считать. Под спойлером матрица и вектор.

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).

678E - Очередной турнир ситхов

Задачу предложил Алексей Дергунов dalex.

Давайте решать задачу динамикой. z_mask, i — наибольшая вероятность выиграть Ивану, если джедаи из маски mask уже хоть раз сражались, а в живых остался только i-й джедай. Для подсчёта динамики переберём следующего джедая (ему придётся сражаться против i-го джедая): .

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(2ⁿn²).

Сложность по памяти: O(2ⁿn).