| Gadgets powered by Google

# Блог Артема Игликова

программирование, соревнования, операционные системы и все такое

- Главная
- Об авторе
- Проекты
- Сейчас…

## Разбор задач 3-го этапа Республиканской олимпиады школьников

Май 17, 2009 – 21:26

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

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

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

Разделы: Олимпиады

## Комментарии (3)

1. narik, Май 28, 2009, 13:16

   большое спасибо!!! оказывается что я задачу мухи решил ну как не правильно(((

   Ответить

2. Maksim, Авг 23, 2009, 13:12

   спасибо за примеры задач

   Ответить

3. Алексей, Авг 24, 2009, 18:30

   спасибо, хорошие примеры

   Ответить

## Оставить комментарий

Имя (обязательно):

E-mail (не публикуется, обязательно):

Вебсайт:

Уведомлять о новых комментариях по e-mail

Отмена