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

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

Задача является вариацией довольно известной математической задачи. Главное – понять, что каждая муха всегда будет двигаться строго к соседке. В этом случае скорости мух всегда будут направлены друг к другу под одним углом, а рассматривая движение с точки зрения какой-то из мух, можно заметить, что на расстояние между ней и соседкой влияет ее скорость и проекция скорости соседки на прямую, содержащую скорость этой мухи. В результате получим, что время, через которое мухи встретятся равно 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;
}

Задача C. Опасный маршрут

Один из вариантов решения – использовать алгоритм Краскала для построения остовного дерева. Уберем из графа все ребра и будем добавлять их обратно в порядке увеличения стоимости. Как только образуется путь из вершины 1 в вершину N – следует остановиться и вывести стоимость последнего добавленного ребра.

Задача D. Горки

В этой задаче также существует множество подходов. Ну а то, что в качестве ответа нужно вывести только сумму высот, добавляется множество алгоритмов, строящих неправильную последовательность, но дающих правильную сумму. Вот один из подходов. Главная проблема в этой задаче – это наличие одинаковых элементов в количестве превышающем (N + 1) / 2. Если таковых элементов нет, то всегда можно построить N / 2 горок с N / 2 наибольшими числам в качестве высот. Если же такие элементы есть, то нужно действовать хитрее. Допустим, что наиболее часто встречающееся число равно K. Если имеются числа, большие K, то используем их в качестве высот горок из двух элементов, один из которых будет равен K. Поместим эти горки в начале последовательности. В оставшейся части также будем строить горки из двух элементов (пока это возможно), но наибольшим элементом в каждой из них будет уже K.

int l = 0;
if (k != m) {
	for (int i = MAXN; i > k; --i) {
		while (c[i] > 0) {
			b[l++] = k;
			--c[i];
			b[l++] = i;
			--c[k];
		}
	}
}
int r = n - 1;
for (int i = 0; i <= k; ++i) {
	while (c[i] > 0) {
		if (r < l) {
			break;
		}
		b[r--] = k;
		--c[k];
		if (r < l) {
			break;
		}
		b[r--] = i;
		--c[i];
	}
}

Задача E. Синоптики

Также несложная задача на использование стека. Пройдем по последовательности слева направо и будем выполнять следующие действия для каждого числа: вытащим из стека все числа, меньшие текущего числа, а затем добавим это число. При этом, число на верхушке стека перед добавлением нового числа будет указывать на искомый день.

Задача F. Телепорт

Построим граф, определяемый условием задачи. При этом в качестве стоимости ребер, означающих маршруты дирижаблей, положим стоимости этих билетов на эти дирижабли, а в качестве стоимости ребер между планетами возьмем большое число, например, 10^6. Затем запустим на этом графе обычный алгоритм Дейкстры. Понятно, что наилучший путь будет использовать как можно меньше переходов между планетами из-за их большой стоимости. Пусть в результате получено число X, тогда количество переходов между планетами будет равно X / 10^6, а стоимость маршрута – X % 10^6.