Олимпиада по информатике 2014

II этап Всеукраинской олимпиады по информатике для 8-11 классов.

Содержание



Фотография

Цветное изображение имеет N цветов. Размер изображения AxB см. Разрешение R точек на дюйм (1 дюйм = 2,54 см).
Определить сколько Кбайт памяти нужно для хранения изображения в несжатом виде?

Входные данные

Первая строка содержит натуральное число N количество цветов. Следующие две строки содержат действительные числа, которые задают размер фотографии. Последняя строка содержит натуральное число, которое задает разрешение. Все числа входного файла по абсолютной величине не превышают 1000000000.

Выходные данные

Единственная строка файла содержит искомый размер фотографии, как действительное число с двумя знаками после запятой.

Пример входных и выходных данных

input.txt output.txt
8
10
15
30
766.29

Решение

Для решения задачи необходимо определить количество бит занимаемая точка и подсчитать их количество. Для определения количества бит используется соотношение n=2k (где n — количество точек, k — количество бит), отсюда

    \[ k=log_{2}n=\frac{ln{n}}{ln{2}} \]

Данная формула используется для определении количества двоичных кодов в бинарном дереве.

n b
2
4
8
16
32

256
65536
16777216
1
2
3
4
5

8
16
24

Компьютеры

Между школами поделили N компьютеров Pentium и M компьютеров Celeron. Сколько было школ, если известно их не менее K и каждая школа получила одинаковое количество компьютеров каждого вида.

Входные данные

Первая строка содержит натуральные числа N, M, K. Все числа входного файла не превышают 1000000000.

Выходные данные

Единственная строка файла содержит найденное количество школ. Если результатов несколько, то вывести все через пробел в возрастающем порядке.

Пример входных и выходных данных

input.txt output.txt
92
138
25
46

Решение

Необходимо найти общие делители чисел M и N, не меньше число K.

Сбор пошлины

Король страны Ариев завоевал N городов на территории соседних государств.
Теперь ему необходимо создать систему сбора пошлины с завоеванных территорий. Он хочет построить такую систему путей между этими городами, чтобы в любой город можно было добраться (возможно, через другие города) из столицы, но на военном положении на транспорт выделяется очень незначительная часть финансов, поэтому суммарная стоимость построенных путей сообщения между городами имеет быть минимальной.

Входные данные

Первая строка входного файла содержит натуральное число N (1≤N≤100) — количество городов в стране, а также целые числа X и Y — координаты столицы.
Следующие N строк содержат через промежуток координаты Xi, Yi завоеванных городов.
Значения координат по модулю меньше 50000.

Выходные данные

Первая строка должна содержать действительное число с тремя знаками после запятой — суммарную стоимость построенных дорог. Считайте, что стоимость единицы длины дороги равна одной условной единицы.
Следующие строки должны содержать в произвольном порядке список построенных дорог в формате:<код города> => <код города>
При этом столицу обозначьте номером 0. Если ответов несколько, выведите одну любой из них.

Пример входных и выходных данных

input.txt output.txt
6 0 0
1 1
-1 1
0 2
1 -1
-1 -1
0 -2
8.485
2 3
3 1
1 0
0 4
4 6
6 5

Решение

Теория графов — каркас минимального веса (остовное дерево).
Определить длины путей по формуле длины отрезка.

    \[ a\left [ i, j \right ] = \sqrt{\left ( x\left [ i \right ] - x \left [ j \right ] \right )^{2} + \left ( y\left [ i \right ] - y \left [ j \right ] \right )^{2}} \]

На основе длин построить нагруженный, неориентированный граф.
На основе алгоритма Прима или Крускала построить каркас минимального веса, который и будет решением задачи.

Расположение городов Карта дорог


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