Polish version    English version  
  Historia OI -> II OI 1994/1995 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
Wyniki III etapu
Wyniki I etapu
Zadania
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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.




Wersja do druku