Украинские Олимпиады
Украинские Олимпиады по Информатике
по Информатике

Соревнования

Информация
Добро пожаловать
Гостевая книга
Обратная связь
О сайте

ACM-олимпиада
Новости
Правила
Задачи
Сдать задачу
Таблица результатов

IOI-олимпиада
Новости
Правила
Последние задачи
Последние результаты
Архив

"Трудно-решаемая" задача
Новости
Правила
Последняя задача
Последние результаты
Архив

Логические игры
Новости
Правила
Виды игр
Последний турнир
Архив

Викторина
Новости
Правила
Последняя викторина
Архив

 
 
Всеукраинские подготовительные сборы Киев'2000

Черно-белые точки

  

 

Задание

Дано 2n точек, размещенных на прямой в целочисленных позициях от 1 до 2n. Среди них n точек черного цвета и n белого. Из этих точек соединением черной и белой образуются n черно-белых пар точек. Для соединения двух точек пары используются две одинаковые вертикальные линии и одна горизонтальная линия, проходящая выше прямой с точками. Все линии должны быть натуральной длины (>0). Линии не должны перекрываться или пересекаться. Задача состоит в нахождении такого разбиения точек на пары, при котором суммарная длина соединяющих линий минимальна. Имя программы point.pas.

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

Входной файл point.dat состоит из двух строк. В первой дано число 1<2n<100. Во второй строка единиц и нулей, которые представляют черные и белые точки соответственно.

Пример входного файла
10
1110100010
Выходные данные

Выходной файл point.sol содержит n+1 строку. В первой строке - найденная длина соединений. В следующих n строках - пара чисел через пробел, обозначающих пару (соединение).

Пример выходного файла
31
1 8
2 7
3 4
5 6
9 10

  

 

Сборник

Олимпиады
Международные
Всесоюзные
Всеукраинские (IV этап)
Разные...

Всеукраинские олимпиады
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002

Отборочные сборы
1992 1993 1994 1996 1997 1998 1999 2000 2001 2002

Международные олимпиады
1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002

Всесоюзные олимпиады
1989 1990 1991 1992

Информация
Список ссылок
Литература
Статьи
Рассылки
Интервью

© Разработано рабочей группой UOI 1998-2002 гг.