Темы
    Информатика(2656 задач)
---> 61 задач <---
Источники --> Личные олимпиады --> Украинские олимпиады
    1999(3 задач)
    2000(5 задач)
    2001(4 задач)
    2002(7 задач)
    2003(3 задач)
    2004(6 задач)
    2005(5 задач)
    2006(6 задач)
    2007(6 задач)
    2008(5 задач)
    2009(6 задач)
    2010(0 задач)
    2011(0 задач)
    2012(0 задач)
    2013(0 задач)
    2016(5 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

 На плоскости расположены два полных бинарных дерева глубины N. Их 2x2N листьев расположены на двух параллельных прямых и пронумерованы слева направо. Листья с одинаковыми номерами в первом и втором деревьях находятся один напротив другого. Между листьями деревьев задано соответствие – каждый из листьев одного дерева имеет ровно один соответствующий ему лист во втором дереве, и наоборот. На рисунке такие соответствия заданы прямыми отрезками между листьями. Такую конструкцию – два дерева вместе с соответствиями между листьями – называют танглеграмом. Танглеграмы, например, используются биологами при исследовании взаимосвязей генов разных видов растений.

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

Напишите программу, которая по информации о соответствии между листьями двух деревьев определит наименьшее возможное количество пересечений отрезков в графическом представлении танглеграма, которое может быть достигнуто путем выполнения операций обмена смежных поддеревьев первого дерева. Если в одной точке пересекаются больше двух отрезков, то под количеством пересечений нужно понимать количество попарных пересечений отрезков. Например, на первом рисунке соответствия 4-8, 5-5 и 6-4 образуют три пересечения.

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

В первой строке входного файла находится натуральное число N (1≤N≤19) – глубина деревьев. Вторая строка содержит 2N разных целых чисел от 1 до 2N, каждое i-ое из которых задает лист второго дерева, который связан отрезком с i-ым листом первого дерева.

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

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

Примеры
Входные данные
3
3 2 1 8 5 4 7 6
Выходные данные
6
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

 >Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных открытий:

  1. Все живые организмы планеты происходят от бактерии Bitozoria Programulis.
  2. Эволюция происходила шаг за шагом (по предположению ученых – во время изменения климата на планете).
  3. На каждом шаге эволюции из каждого вида образовывались ровно два подвида, а предыдущий вид исчезал.
  4. Если считать появление бактерии Bitozoria Programulis первым шагом эволюции, то существующие сейчас живые организмы находятся на N-ом шаге.

Чтобы не придумывать названия во время исследований, ученые пронумеровали все виды организмов, которые когда-либо существовали на планете. Для этого они нарисовали дерево эволюции с корнем Bitozoria Programulis, которая получила номер 1. Далее нумеровали виды каждого шага эволюции слева направо. Таким образом непосредственные подвиды Bitozoria Programulis получили номера 2 и 3. Следующими были занумерованы виды третьего шага эволюции – подвиды вида 2 получили номера 4 и 5, а вида 3 – номера 6 и 7, и т.д.

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

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

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

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

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

Примеры
Входные данные
4
15
12
Выходные данные
3
Входные данные
18
233016
233008
Выходные данные
14563
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Торговец владеет тремя видами товаров: алмазы, яблоки и шелк. Для каждого товара известна стоимость в золотых монетах за единицу веса и его количество у торговца.

В стране, где живет торговец, есть N городов, которые пронумерованы от 1 до N. Родной город торговца имеет номер 1, а столица – номер N. Чтобы добраться до столицы, где торговец может продать товар, ему нужно проехать определенным маршрутом через другие города. Между некоторыми парами городов существуют дороги, проезд по которым стоит определенного количества золотых. В каждом городе взимается налог за провоз каждого из видов товара, заданный в процентах от стоимости провезенного через город товара. Известно, что выехав из любого города, торговец не может в него вернуться. Любые два города соединены не более чем одной дорогой.

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

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

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

Первая строка входного файла содержит два целых числа N (2≤N≤500) и M (M1) – количество городов и дорог между ними. Вторая строка содержит три целых неотрицательных числа, которые соответствуют количествам единиц веса алмазов, яблок и шелка, принадлежащим торговцу. Третья строка содержит три целых неотрицательных числа – стоимости единиц веса алмазов, яблок и шелка соответственно. Последующие строки с 4-ой по N+1 содержат по три целых числа от 0 до 100 включительно, которые соответствуют процентам от стоимости алмазов, яблок и шелку, которые взимаются, соответственно, в городах от 2 до N-1 в качестве налога. В списке городов не учтены родной город торговца 1 и столица N, так как в них с торговца не взимают налог. Последующие M строк содержат по три целых неотрицательных числа, первые два из которых от 1 до N задают пару городов, между которыми проложена дорога, а третье – стоимость проезда по этой дороге. Дороги ведут в направлении от города, указанного первым, до того, который указан вторым. Количества единиц веса каждого из видов товара у торговца, стоимости товаров и цены проезда по дорогам не превышают 100.

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

Единственная строка выходного файла должна содержать одно число – точное значение найденной максимальной прибыли от поездки в столицу. Ответ всегда должен содержать ровно два знака после точки. В случаях, когда торговец не может получить прибыль или добраться до столицы по существующим дорогам, требуется вывести 0.00

Примеры
Входные данные
4 4
10 5 20
100 5 12
15 40 25
90 20 10
1 2 5
1 3 10
3 4 10
2 4 15
Выходные данные
1025.00
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости заданы N разных окружностей. Две окружности пересекаются, если они имеют хотя бы одну общую точку.

Напишите программу, которая по координатам центров окружностей и их радиусам найдет пару пересекающихся окружностей.

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

В первой строке входного файла содержится целое числоN (1≤N≤10 000) . В каждой из последующих N строк содержатся три натуральных числа X, Y, R меньших 10 000, которые задают координаты центра окружности (X, Y) и его радиус R.

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

Единственная строка выходного файла должна содержать пару номеров пересекающихся окружностей, либо единственное число 0, если никакие две окружности не пересекаются. Окружности нумеруются соответственно порядку во входном файле, начиная с 1 до N. Если существует несколько пар пересекающиеся окружностей, выведите любую из них. Элементы пары могут быть выведены в произвольном порядке.

Примеры
Входные данные
5
5 10 4
6 20 3
10 15 3
12 8 2
13 13 1
Выходные данные
5 3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Единственная строка входного файла содержит одно целое число N (1N≤109) – номер секунды.

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

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

Примеры
Входные данные
7
Выходные данные
4
Входные данные
5
Выходные данные
2

Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест