Темы
    Информатика(2656 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 33 34 35 36 37 38 39 >> Отображать по:
#111225
Мозаика
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

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

В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа Ai и Bi , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ Ai, Bi ≤ 109, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N1 и N2 – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).

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

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

Примечание

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

  1. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.

  2. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.

  3. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.

  4. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

Примеры
Входные данные
4
2 2
1 2
1 3
2 3
2
2 3
2 4
Выходные данные
0 0
4 2
#111226
Театр начинается с актеров
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Участники олимпиады пришли в казанский театр на спектакль, где играют N неизвестных для них актеров. В фойе театра висят портреты всех актеров труппы, которая в полном составе задействована в спектакле. Портреты не подписаны. Зрителям раздали программки, в которых для каждого действия спектакля приводится список фамилий участвующих в нем актеров, но не указаны их роли. Театрал Виталий решил узнать, как выглядит каждый из актеров, упомянутых в программке. Для этого в антракте после каждого действия он выходил в фойе и сопоставлял портреты с увиденными актерами. Требуется написать программу, которая по заданному числу актеров N и списку фамилий актеров, участвующих в каждом из M действий, определяет номер действия, после которого впервые становится возможным установить соответствие между фамилией актера из программки и его портретом.

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

Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров Ki, участвующих в i–ом действии (1 ≤ Ki ≤ N, K1 + K2 + ... + KM ≤ 100 000), а затем Ki различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.

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

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

Примечание

В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1. Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.

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

  1. (оценивается в 30 баллов) Количество актеров N не превосходит 100, количество действий M не превосходит 100, K1 + K2 + ... + KM ≤ 100.

  2. (оценивается в 30 баллов) Количество актеров N не превосходит 10 000, количество действий M не превосходит 10 000, K1 + K2 + ... + KM ≤ 10 000.

  3. (оценивается в 40 баллов) Количество актеров N не превосходит 100 000, количество действий M не превосходит 100 000, K1 + K2 + ... + KM ≤ 100 000.

Примеры
Входные данные
3 3
2 1 2
2 3 2
2 1 2
Выходные данные
2 2 1
Входные данные
5 3
3 1 2 3
3 2 1 3
2 1 3
Выходные данные
0 3 0 0 0
Входные данные
4 3
1 1
1 3
1 2
Выходные данные
1 3 2 3
#111227
Ордынское войско
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

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

В первой строке входного файла задано натуральное число N – общее количество воинов (1 ≤ N ≤ 15). Во второй строке задано натуральное число K – количество телохранителей хана (1 ≤ K ≤ N). В третьей строке через пробел указаны K различных натуральных чисел, не превосходящих N, – номера телохранителей хана в порядке возрастания.

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

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

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

  1. (оценивается в 40 баллов) 1 ≤ N ≤ 8.

  2. (оценивается в 10 баллов) 9 ≤ N ≤ 10.

  3. (оценивается в 10 баллов) N = 11.

  4. (оценивается в 10 баллов) N = 12.

  5. (оценивается в 10 баллов) N = 13.

  6. (оценивается в 10 баллов) N = 14.

  7. (оценивается в 10 баллов) N = 15.

Примеры
Входные данные
5
3
1 3 4
Выходные данные
11
Входные данные
3
3
1 2 3
Выходные данные
1
Входные данные
1
1
1
Выходные данные
1
#111454
Участки на Уране
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Уран наконец-то освоен! МОЗГу удалось и на этой мертвой планете поставить нужные преобразователи. Теперь на этой планете можно проводить некоторое время без вреда для здоровья. Чем и решили воспользоваться межпланетные туристические фирмы. Одна из них - «С нами хоть на Луну» - решила потратить весь свой фонд на покупку квадратных участков на Уране. Дабы не потерять в прибыли — нужно потратить весь фонд до монеты, а чтобы иметь меньше проблем с Межпланетной налогово-таможенной службой, было бы здорово купить наименьшее количество участков. Цена 1 кв.м. планеты - 1 монета.

Помогите решить проблему турфирмы.

Формат входного файла

В единственной строке задано одно число — количество монет в фонде турфирмы. Количество монет не превышает 100.

Формат выходного файла

Выведите минимальное количество квадратных участков, которое можно купить, потратив все деньги.

Пояснение к примеру
15 = 3 * 3 + 2 * 2 + 1 * 1 + 1 * 1
Примеры
Входные данные
15
Выходные данные
4
#111455
Щит
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

МОЗГ организация авторитетная. Ей поручают очень важные разработки. В данный момент многие из планетарных союзов в галактике заказывают разработку сторожевого силового щита вокруг их планет. И первой задачей при постройке такого щита является заказ ультраплотной плазмы. Ультраплазма невероятно дорога, поэтому заказывать с запасом — дорогого стоит.

Представим себе планеты как окружности с некоторым одинаковым радиусом, тогда щит нужно построить так:

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

Формат входного файла

В первой строке находятся два числа — количество гвоздей \(N\), \(1 \leq N \leq \)100, и вещественное число \(R\) — радиус планет.

Далее на входе располагаются еще \(N\) строк, в каждой из которых записана через пробел пара вещественных координат очередной планеты; координаты не превосходят по абсолютной величине числа 100. Описания планет приводятся в порядке обхода вершин многоугольника (либо по часовой стрелке, либо против часовой стрелки), начиная с произвольного.

Формат выходного файла

Выведите вещественное число, округлённое до двух знаков после запятой — длину сечения щита.

Примеры
Входные данные
4 1
0.0 0.0
2.0 0.0
2.0 2.0
0.0 2.0
Выходные данные
14.28
Страница: << 33 34 35 36 37 38 39 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест