678A - Johny Likes Numbers

Задачу предложил Әбдірахман Исмаил 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 - The Same Calendar

Задачу предложил Артур Яворски 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 - Joty and Chocolate

Задачу предложил 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(1).