Olimpiada Informatyczna

II Olimpiada Informatyczna 1994/95

Zadanie: OPT

Autor: Tomasz Śmigielski, Piotr Krysiuk

Optymalizacja dysku

Zawody I stopnia

Plik źródłowy:	`OPT.???` (np. `pas`, `c`, `cpp`)
Plik wykonywalny:	`OPT.exe`
Plik wejściowy:	`OPT.in`
Plik wyjściowy:	`OPT.out`

Dysk składa się z N sektorów ponumerowanych kolejno od 1 do N. Dowolny niepusty ciąg sektorów o kolejnych numerach nazywamy blokiem. Długość bloku to liczba zawartych w nim sektorów. Bloki są rozłączne, jeśli nie mają wspólnego sektora.

Na dysku są zapisane pliki. Jeden plik może być zapisany w wielu sektorach, które nie muszą tworzyć jednego bloku. Aby prawidłowo odtworzyć plik trzeba odczytać te sektory we właściwej kolejności. Ten ciąg sektorów wyznacza ciąg rozłącznych bloków, z których każdy zawiera jeden lub więcej sektorów. Sektory wewnątrz każdego bloku czyta się według kolejności numerów.

Opis rozmieszczenia pliku na dysku jest ciągiem par liczb całkowitych dodatnich. Każda taka para składa się z numeru początkowego sektora bloku oraz długości tego bloku.

Przykład
Ciąg par:
7 3
2 1
5 2
informuje, że treść pliku należy odczytać kolejno z sektorów o numerach: 7, 8, 9, następnie: 2, a następnie: 5, 6.

Każdy sektor na dysku może być wolny albo jest w nim zapisana część tylko jednego pliku (lub jeden cały plik).

Każdy plik ma unikalny identyfikator - dodatnią liczbę całkowitą z zakresu od 1 do P, gdzie P jest liczbą plików na dysku.

Dysk jest zoptymalizowany, gdy:

każdy plik jest pamiętany w jednym bloku (w kolejnych sektorach),
plik o mniejszym identyfikatorze zajmuje sektory o niższych numerach, niż każdy plik o wyższym identyfikatorze,
każdy sektor wolny ma numer większy niż każdy sektor zajęty.

Na dysku można wykonywać następujące operacje:

kopiowanie zawartości bloku do rozłącznego z nim bloku o tej samej długości,
zamiana zawartości dwóch rozłącznych bloków o tej samej długości.

Kopiowanie bloku o długości t trwa t mikrosekund.

Zamiana zawartości dwóch bloków o długości t trwa 2*t mikrosekund.

Polecenie kopiowania pliku ma postać:
K początek_bloku nowy_początek_bloku długość_bloku

Polecenie zamiany ma postać:
Z początek_bloku1 początek_bloku2 długość_bloku
gdzie początek_bloku oznacza numer pierwszego sektora bloku.

Zadanie
Ułóż program, który:

wczytuje liczbę sektorów i liczbę plików oraz opisy ich rozmieszczeń na dysku z pliku tekstowego OPT.IN,
sprawdza, czy dysk jest zoptymalizowany. Jeśli tak, to zapisuje w pliku OPT.OUT tylko jeden wyraz NIC. Jeśli nie, to generuje odpowiedni ciąg poleceń powodujących optymalizację dysku w taki sposób, aby czas optymalizacji był jak najkrótszy (nie jest istotna liczba poleceń, tylko łączny czas ich wykonania), po czym zapisuje ten ciąg poleceń w pliku tekstowym OPT.OUT.

Wejście

W pierwszym wierszu pliku danych OPT.IN są zapisane dwie liczby całkowite dodatnie: liczba sektorów na dysku N, nie większa niż 10000, oraz liczba plików P. Dalej w kolejnych wierszach następują opisy rozmieszczenia plików na dysku. Każdy opis pliku zawiera w pierwszym wierszu dwie liczby: identyfikator pliku z zakresu od 1 do P oraz dodatnią liczbę rozłącznych bloków, w których zapisany jest ten plik. W następnych wierszach znajduje się opis rozmieszczenia pliku w postaci odpowiedniego ciągu par liczb całkowitych dodatnich, każda para w osobnym wierszu. Liczby w wierszach są oddzielone pojedynczymi odstępami. Dane w pliku OPT.IN są zapisane poprawnie i Twój program nie musi tego sprawdzać.

Wyjście

Plik OPT.OUT ma zawierać tylko jeden wyraz NIC, gdy dysk jest już zoptymalizowany, albo ciąg poleceń, każde w osobnym wierszu. Każde polecenie musi być zapisane zgodnie z podanym poniżej formatem: najpierw duża litera K albo Z, pojedynczy odstęp, potem trzy liczby całkowite dodatnie oddzielane pojedynczymi odstępami.

Przykład

Dla pliku OPT.IN:
200 2
2 2
51 10
41 10
1 2
71 20
11 20

plik OPT.OUT może mieć postać:
K 21 31 10
K 11 21 10
K 71 1 20
Z 41 51 10

Twój program powinien szukać pliku OPT.IN w katalogu bieżącym i tworzyć plik OPT.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę OPT.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku OPT.EXE.