Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Индивидуальная олимпиада по информатике и программированию (ИОИП)
    Заключительный этап 2009(4 задач)
    Заключительный этап 2010(4 задач)
    Заключительный этап 2012(4 задач)
    Заключительный этап 2013(5 задач)
    Заключительный этап 2015(5 задач)
Страница: 1 Отображать по:
#1254
Монотонная последовательность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c1, . . . , cn называется строго возрастающей, если выполняются неравенства c1 < c2 < … < cn, и строго убывающей, если выполняются неравенства c1 > c2 > … > cn.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100000). Каждая из последующих n строк описывает одну карточку и содержит два числа — ai написано на ее лицевой стороне, а bi — на оборотной. Все числа ai и bi находятся в диапазоне от 1 до 109.

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

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

Комментарий к примеру тестов

В первом примере для достижения цели Петя может перевернуть карточки со второй по третью.

В третьем примере можно, например, первым действием перевернуть карточки со второй по шестую, а вторым — четвертую карточку.

Примеры
Входные данные
3
3 4
1 2
4 1
Выходные данные
1
Входные данные
3
1 2
4 1
3 4
Выходные данные
-1
Входные данные
6
1 2
3 2
2 3
4 5
6 5
5 6
Выходные данные
2
#3020
Схема игры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Например, схема игры 5-3-2 означает, что в команде пять защитников, три полузащитника и два нападающих. В соответствии с современными представлениями на схему игры накладываются следующие ограничения: должно быть не менее одного и не более пяти защитников, не менее одного и не более пяти полузащитников и не более трех нападающих. Отметим, что нападающих может в команде и не быть совсем. Будем рассматривать только такие схемы.

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

Будем также считать, что игрок в некоторый момент времени находится в линии полузащиты, если он находится на расстоянии не более 20 метров от центральной линии. Соответственно, игрок находится в линии защиты, если он находится не более чем в 40 метрах от «своей» лицевой линии, и в линии нападения, если находится не более чем в 40 метрах от «чужой» лицевой линии.

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

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

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

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

Входной файл содержит десять строк, содержащих по два целых числа xi и yi каждая, — координаты каждого из игроков команды (0 ≤ xi ≤ 120, xi ≠ 40, xi ≠ 80, 0 ≤ yi ≤ 80).

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

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

Примеры
Входные данные
97 0
13 18
2 6
119 11
42 21
72 80
75 78
106 45
22 67
28 47
Выходные данные
9
2-5-3
3-5-2
3-4-3
4-5-1
4-4-2
4-3-3
5-4-1
5-3-2
5-2-3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест