<ПРЕД Задача:
СЛЕД>
Задачу решили 125 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Дефрагментация

Time limit = 5 секунд

Вам нужно дефрагментировать диск. Информация на диске хранится кластерами. Каждый файл занимает целое положительное число кластеров. На диске всего N кластеров, среди них некоторые пустые.

Кластеры пронумерованы 1, 2, .... N.

Вы можете выполнять операцию переноса информации из одного кластера в другой.

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

Вход. В первой строчке указаны размер диска N и количество файлов K (1 ≤ N, K ≤ 10000).

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

Точно есть хотя бы один свободный кластер. Номера кластеров не повторяются.

Выход. Нужно вывести "No optimization needed" или вывести L строчек с описанием L операций переноса.

Каждая строчка имеет вид

Pi Qi

что соответсвует операции переноса информации из Pi-ого кластера в Qi.

Число L должно быть минимальным.

Вход#1
20 3
4 2 3 11 12
1 7
3 18 5 10

Выход#1
2 1
3 2
11 3
12 4
18 6
10 8
5 20
7 5
20 7

Автор:

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 18.232.133.231