ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Личное первенство УрГУ 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Космический покер

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Правила игры в космический покер так трудны, что объяснять их здесь нет никакого смысла. Скажем только, что в начале игры каждый игрок получает N (N ≤ 20) карт. Каждая карта имеет достоинство (целое число от 1 до 100) и масть (целое число от 1 до 10). Все карты различны. Масти с нечетным номером называются синими, а масти с четным номером — желтыми. Карты сдаются специальным автоматом, который гарантирует выполнение Правила Штайнпупера: если игроку в сдаче попались карты X различных синих мастей и Y различных желтых мастей, то |XY| ≤ 1. Карты сдаются по одной, игрок сразу берет их со стола себе в руку, слева направо.
Чтобы сориентироваться в своих картах игрок, перед началом каждой партии, раскладывает карты по мастям. Это значит, что последовательностью атомарных операций игрок добивается такого расположения карт, при котором:
  1. Все карты одной масти лежат подряд;
  2. Синие и желтые масти чередуются (это всегда возможно благодаря правилу Штайнпупера);
  3. Внутри масти карты упорядочены либо по возрастанию, либо по убыванию достоинств, причем все масти упорядочены одинаково.
Атомарная операция заключается в том, что игрок берет одну из карт и перемещает ее на любое место (т.е., на самую левую позицию, на самую правую или между любыми двумя картами). Естественно, разложить карты по мастям можно многими разными способами. Опытного игрока устроит любой из них. Главное — минимизировать количество операций — иначе руки устают уже к концу второго галактического года игры.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
5
10 1
12 2
8 2
4 4
7 4
2
Автор задачи: Леонид Волков
Источник задачи: Личное первенство УрГУ 2004
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1284. Космический покер