Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Седьмая личная олимпиада"

Задача A. Высота треугольника

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Задан треугольник длинами своих сторон. Найдите длину самой короткой из его высот.

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

Входной файл INPUT.TXT содержит три натуральных числа: A, B и C – длины сторон треугольника, не превосходящие 1000. Гарантируется, что такой треугольник существует и имеет ненулевую площадь.

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

В выходной файл OUTPUT.TXT выведите ответ на задачу с точностью, не худшей 10-5.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 10.8660254
23 4 52.4

Задача B. ЕГЭ

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Соня учится в одиннадцатом классе, и в этом году ей надо сдавать единый государственный экзамен по информатике. Она решила начать готовиться заранее и стала решать задачи из вариантов прошлых лет.

Во многих заданиях требуется перевести число из одной системы счисления в другую. Соня с легкостью справляется с такими заданиями, но недавно в одном из вариантов ей попалась задача, которая показалась довольно интересной: число x, заданное в десятичной системе счисления, требуется перевести в (−3)-ичную систему счисления.

Формально, записью числа в (−3)-ичной системе счисления называется набор чисел an-1, an-2, … , a0, каждое из которых равно 0, 1 или 2, причем n = 1 или an−1 ≠ 0 и выполнено равенство:

Например, 7 в (−3)-ичной системе счисления представляется как (111)−3: действительно, 1∙(−3)2+1∙(−3)1+1∙(−3)0 = 9 – 3 + 1 = 7.

В задаче предлагается перевести в (−3)-ичную систему счисления только одно число, но Соне стало интересно решение этой задачи в общем случае. После долгих раздумий она обратилась к вам за помощью. Помогите ей перевести заданное число в (−3)-ичную систему счисления.

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

Входной файл INPUT.TXT содержит одно целое число x – число, которое Соня хочет представить в (−3)-ичной системе счисления (−1018 ≤ x ≤ 1018).

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

В выходной файл OUTPUT.TXT выведите сокращенную запись числа x в (−3)-чной системе счисления без лидирующих нулей.

Примеры

INPUT.TXTOUTPUT.TXT
17111
2-521

Задача C. Раскраска карты

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество стран на карте (N ≤ 20). В следующих N строках располагается матрица смежности: каждая (i+1)-я строка содержит разделенные пробелом N цифр – информацию о смежных государствах i-й страны. В (i+1)-й строке в j-й позиции записана цифра 1, если страны с номерами i и j имеют общую границу и 0 – в противном случае. Страны нумеруются от 1 до N. Гарантируется, что такое расположение стран возможно отобразить на плоскости.

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

В выходной файл OUTPUT.TXT выведите N целых чисел от 1 до M – цвета стран после раскраски. Здесь M – минимально возможное количество цветов, необходимых для раскраски. Если возможных вариантов раскраски несколько, выведите любой из вариантов.

Примеры

INPUT.TXTOUTPUT.TXT
13
0 1 0
1 0 0
0 0 0
1 2 1
217
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0
1 2 1 1 1 2 3 1 2 3 1 2 1 2 1 2 3

Система оценки

Решения, использующие раскраску в два цвета и менее, будут оцениваться в 50 баллов.


Задача D. Восстановление перестановки

(Время: 2 сек. Память: 16 Мб Баллы: 100)

Знаменитая гипотеза Улама утверждает, что если рассмотреть граф G и построить мультимножество Gmin графов, получаемых из G удалением по очереди каждой из его вершин вместе со всеми инцидентными ей ребрами, то граф G можно однозначно восстановить по Gmin. Гипотеза Улама до сих пор не доказана, не известно и контрпримера.

В этой задаче мы рассмотрим аналогичную задачу для перестановок. Рассмотрим перестановку a = {a1, a2, ..., an} чисел от 1 до n. Обозначим как a/i перестановку n-1 чисел, полученных из a удалением числа i и уменьшением на единицу всех чисел, больших i. Например, если a = {1, 3, 5, 2, 6, 4}, то a/2 = {1, 2, 4, 5, 3}.

Вам заданы в некотором порядке перестановки a/1, a/2, ..., a/n. Требуется восстановить исходную перестановку a.

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

Первая строка входного файла INPUT.TXT содержит n – размер исходной перестановки (5 ≤ n ≤ 300). Следующие n строк содержат по n-1 числу каждая и задают a/i для всех i в некотором порядке.

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

В выходной файл OUTPUT.TXT выведите n целых чисел – перестановку a. Гарантируется, что такая перестановка существует.

Пример

INPUT.TXTOUTPUT.TXT
16
1 3 5 2 4
1 3 4 2 5
1 2 4 5 3
2 4 1 5 3
1 4 2 5 3
1 3 2 5 4
1 3 5 2 6 4

Пояснение

В приведенном примере перестановки заданы в следующем порядке: a/6, a/4, a/2, a/1, a/3 и a/5.



Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru