II Olimpiada Informatyczna 1994/95
|
Zadanie: OPT
|
Autor: Tomasz Śmigielski, Piotr Krysiuk
|
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:
Na dysku można wykonywać następujące operacje:
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:
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.