Записки программиста

Олимпиада прошла давно, но немного времени для разбора нашлось только сейчас. Архив олимпиады (задачи, тесты и решения) можно найти где обычно.

Задача А. Мухи

Задача является вариацией довольно известной математической задачи. Главное – понять, что каждая муха всегда будет двигаться строго к соседке. В этом случае скорости мух всегда будут направлены друг к другу под одним углом, а рассматривая движение с точки зрения какой-то из мух, можно заметить, что на расстояние между ней и соседкой влияет ее скорость и проекция скорости соседки на прямую, содержащую скорость этой мухи. В результате получим, что время, через которое мухи встретятся равно T = D / (V + V cos(? – 2 ? / N)). Ну а расстояние, которое пройдет каждая из мух, легко вычисляется по магической формуле: S = VT = D / (1 + cos(? – 2 ? / N)).

Задача B. Числа

Из-за небольших ограничений задачу можно было решать множеством разных способов. Один из них – воспользоваться довольно стандартным приемом в таких задачах. Сначала немного преобразуем задачу: посчитаем, сколько раз будет выписана каждая цифра от 1 до 9, а затем посчитаем сумму. Заметим, что F(A, B, Y) = F(1, B, Y) – F(1, A – 1, Y), где A, B – границы интервала, а Y – цифра, количество которой считается. Теперь научимся считать F(1, X, Y). Для этого сначала предподсчитаем D[N] = F(1, 10^N – 1, 1). Это несложно делается по рекуррентному соотношению D[N] = D[N - 1] * 10 + 10 ^ (N – 1). Далее нужно разложить X на цифры и считать количество чисел с заданным префиксом, который нужно перебирать. Здесь проще привести код:

i64 count(i64 x, int y) {
	i64 result = 0;
	int a[20];
	int n = 0;
	if (x == 0) return 0;
	do {
		a[n++] = x % 10;
		x /= 10;
	} while (x > 0);
	int t = 0;
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < a[i]; ++j) {
			if (j == y) {
				++t;
			}
			result += D[i] + t * B[i];
			if (j == y) {
				--t;
			}
		}
		if (a[i] == y) {
			++t;
		}
	}
	result += t;
	return result;
}

(далее…)