Задачи 1 тура областной олимпиады по информатике 2010

1. Соревнования картингистов

Ограничения: время – 2s, память – 64M Послать решение Посылки Темы Обсудить (0)

После очередного этапа чемпионата мира по кольцевым автогонкам на автомобилях с открытыми колесами Формула-А гонщики собрались вместе в кафе, чтобы обсудить полученные результаты. Они вспомнили, что в молодости соревновались не на больших болидах, а на картах — спортивных автомобилях меньших размеров.

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

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

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

Формат входных данных

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

Вторая строка содержит m положительных целых чисел, где каждое число — это время прохождения данным участником каждого из m кругов трассы (каждое из этих чисел не превосходит 1000). Длина имени каждого участника не превышает 255 символов.

Формат выходных данных

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

Пример ввода

5 3
Sumaher
2 1 1
Barikelo
2 1 2
Olonso
1 2 1
Vasya
1 1 1
Fedya
1 1 1 

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

Fedya

Источник: региональный этап Всероссийской олимпиады по информатике 2009/2010, http://neerc.ifmo.ru/school/

2. Дипломы

Ограничения: время – 2s, память – 64M Послать решение Посылки Темы Обсудить (0)

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него скопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Поворачивать дипломы на 90 градусов не разрешается. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

Формат входных данных

Входной файл содержит три целых числа: w, h, n (1 ≤ w, h, n ≤ 10⁹).

Формат выходных данных

В выходной файл необходимо вывести ответ на поставленную задачу.

Пример ввода

2 3 10

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

9

Система оценивания
Решения, правильно работающие только при w, h, n ≤ 1000, будут оцениваться из 40 баллов.
Иллюстрация к примеру

Источник: региональный этап Всероссийской олимпиады по информатике 2009/2010, http://neerc.ifmo.ru/school/

3. Булева функция

Ограничения: время – 2s, память – 64M Послать решение Посылки Темы Обсудить (0)

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

Если задана булева функция f и набор из N булевых значений a₁, a₂, …, a_N, то результат цепного вычисления этой булевой функции определяется следующим образом:

• если N = 1, то он равен a₁;
  
• если N > 1, то он равен результату цепного вычисления булевой функции f для набора из (N−1) булевого значения f(a₁,a₂), a₃, …, a_N, который получается путем замены первых двух булевых значений в наборе из N булевых значений на единственное булево значение — результат вычисления функции f от a₁ и a₂.

Например, если изначально задано три булевых значения: a₁ = 0, a₂ = 1, a₃ = 0, а функция f — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть, 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

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

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

Формат входных данных

Первая строка входного файла содержит одно натуральное число N (2 ≤ N ≤ 100 000).

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

Формат выходных данных

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

Пример ввода 1

4
0110

Пример вывода 1

1011

Пример ввода 2

5
0100

Пример вывода 2

11111

Пример ввода 3

6
0000

Пример вывода 3

No solution

Пояснения к примерам
В первом примере процесс вычисления цепного значения булевой функции f происходит следующим образом:
1011 → 111 → 01 → 1
Во втором примере вычисление цепного значения булевой функции f происходит следующим образом:
11111 → 0111 → 111 → 01 → 1
В третьем примере получить цепное значение булевой функции f, равное 1, невозможно.
Система оценивания
Решения, правильно работающие только при N ≤ 20, будут оцениваться из 40 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2009/2010, http://neerc.ifmo.ru/school/

4. Кольцевая автодорога

Ограничения: время – 2s, память – 64M Послать решение Посылки Темы Обсудить (0)

К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим еще в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от нее. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

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

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

Формат входных данных

Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: x_i и y_i — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвертая — четвертую. Никакие две достопримечательности не находятся в одной точке.

Все числа во входном файле не превосходят 100 по абсолютной величине.

Формат выходных данных

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

На второй строке требуется вывести координаты центра дороги минимальной длины и ее радиус. Если существует несколько разных способов построить дорогу минимальной длины, необходимо вывести любой из них. Координаты центра и радиус дороги должны быть выведены с точностью не хуже 10⁻⁵.

Пример ввода 1

0 0
0 1
1 0
2 2

Пример вывода 1

7
1.5 0.5 1.14412281

Пример ввода 2

0 0
0 1
1 0
1 1

Пример вывода 2

Infinity
0.5 0.5 0.0

Источник: региональный этап Всероссийской олимпиады по информатике 2009/2010, http://neerc.ifmo.ru/school/