Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 12 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада --> 9-11 классы
    2003(8 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(19 задач)
    2008(19 задач)
    2009(18 задач)
    2010(18 задач)
    2011(18 задач)
    2012(19 задач)
    2013(19 задач)
    2014(20 задач)
    2015(21 задач)
    2016(20 задач)
Страница: 1 2 3 >> Отображать по:
#28
Современники
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Группа людей называется современниками, если был такой момент, когда они могли собраться все вместе и обсуждать какой-нибудь важный вопрос. Для этого в тот момент, когда они собрались, каждому из них должно было уже исполниться 18 лет, но еще не исполниться 80 лет.

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

Будем считать, что в день своего 18-летия человек уже может принимать участие в такого рода собраниях, а в день 80-летия, равно как и в день своей смерти, — нет.

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

Сначала на вход программы поступает число N — количество людей (1≤N≤10000). Далее в N строках  вводится по шесть чисел — первые три задают дату (день, месяц, год) рождения, следующие три — дату смерти (она всегда не ранее даты рождения). День (в зависимости от месяца, а в феврале — еще и года) от 1 до 28, 29, 30 или 31, месяц — от 1 до 12, год — от 1 до 2005.

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

Программа должна вывести все максимальные множества современников. Каждое множество должно быть записано на отдельной строке и содержать номера людей (люди во входных данных нумеруются в порядке их задания, начиная с 1). Номера людей должны разделяться пробелами.

Никакое множество не должно быть указано дважды.

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

Гарантируется, что входные данные будут таковы, что размер  выходных данных  для правильного ответа не превысит 2 Мб.

Оценка задачи

1 балл получат программы, правильно решающие задачу для случая N≤100.

Примеры
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
3
Входные данные
3
2 5 1968 13 11 2005
1 1 1 1 1 30
1 1 1910 1 1 1990
Выходные данные
2 
1 3
Входные данные
3
2 5 1988 13 11 2005
1 1 1 1 1 10
2 1 1910 1 1 1928
Выходные данные
0
#37
\"Сортировка\" с конфеткой
  

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

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

Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Требуется вывести массив после сортировки.

Примеры
Входные данные
4
1 4 2 3
2
4 3
1 2
Выходные данные
1 2 4 3
#39
Обувной магазин
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

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

Выведите единственное число — максимальное количество пар обуви.

Примеры
Входные данные
60
2
60 63
Выходные данные
2
Входные данные
26 
5
30 35 40 41 42
Выходные данные
3
#862
Перекраска N-угольника
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.

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

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

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

Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.

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

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

Примеры

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

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

3

–1

4

1 3

1
#864
Медиана объединений
  
Дано N последовательностей. Требуется для каждой пары последовательностей найти медиану объединения этих последовательностей.

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

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

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

Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример 

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

3 6

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
	

	

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

7

10

9
Страница: 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест