cho.sh

익스텐트와 디스크 조각 모음

시간 제한1초메모리 제한128 MB

문제

현대 파일 시스템은 파일을 항상 연속된 위치에 저장하지는 않는다. 대신 파일을 익스텐트(extent) 라고 부르는 조각으로 나누며, 각 익스텐트는 디스크 위 거의 아무 곳에나 놓일 수 있다. 하나의 익스텐트는 물리 디스크의 단위인 블록(block) 한 개 이상을 연속으로 차지한다. 서로 다른 파일은 블록이나 익스텐트를 절대 공유하지 않으며, 사용되지 않는 빈 블록이 남아 있을 수 있다.

이렇게 파일 데이터가 흩어져 있으면, 파일의 모든 블록이 순서대로 붙어 있어 하나의 익스텐트를 이룰 때보다 접근이 느려진다. 그래서 많은 파일 시스템은 조각 모음(defragmentation), 즉 각 파일의 블록이 순서대로 이어지도록 파일을 재배치하는 기능을 지원한다.

RAD's Awesome Dynamic Filesystem(줄여서 RADfs)에서 파일은 몇 개의 익스텐트든 차지할 수 있고, 각 익스텐트는 반드시 서로 붙어 있는 블록 두 개 이상으로 이루어진다. 익스텐트의 첫 블록은 그 익스텐트에 대한 메타데이터를 담고, 나머지 블록은 파일 데이터의 일부를 담는다. 예를 들면:

RADfs.doc: 37-38,102-114,23-47

여기서 RADfs.doc는 디스크에서 40개의 블록을 차지한다($2 + 13 + 25$). 하지만 파일 자체의 데이터는 37블록뿐이다(익스텐트마다 메타데이터 블록이 하나씩 들어가므로 $40 - 3 = 37$). 이 파일이 가질 수 있는 가장 작은 디스크 점유 크기는 38블록(데이터 37블록 + 메타데이터 1블록)이며, 이는 파일 전체가 하나의 익스텐트에 담길 때에만 가능하다. 예를 들면:

RADfs.doc: 115-152

이제 메타데이터 블록(115) 뒤로 37개의 데이터 블록이 하나의 익스텐트에 이어진다.

RADfs 팀은 RADical Defragmentation Daemon(줄여서 RADDD) 도 만들었다. 여유 공간이 충분하다면, 간단한 두 단계 알고리즘만으로도 파일이 차지하는 익스텐트 수를 크게 줄인다.

RADDD의 한 번의 패스(pass) 는 다음과 같이 동작한다.

1단계("뒤로 보내기"). 이번 패스의 이 단계에서 아직 처리되지 않은 모든 파일을, 현재 차지한 첫 블록 번호의 오름차순으로 처리한다.

  • 파일과 메타데이터 블록 하나를 함께 담을 수 있을 만큼 큰, 즉 $(\text{데이터 블록 수}) + 1$개의 연속된 빈 블록으로 이루어진 구간 중 디스크 끝에 가장 가까운 것을 찾는다.
  • 그런 구간이 있으면, 파일을 디스크 끝에 최대한 가깝게 붙여 그 블록들로 옮기고, 원래 블록을 빈 것으로 표시한다.
  • 없으면 파일을 그대로 둔다.

2단계("앞으로 보내기"). 이번 패스의 이 단계에서 아직 처리되지 않은 모든 파일을, 현재 차지한 마지막 블록 번호의 내림차순으로 처리한다.

  • 파일과 메타데이터 블록 하나를 함께 담을 수 있을 만큼 큰 연속된 빈 블록 구간 중 디스크 처음에 가장 가까운 것을 찾는다.
  • 그런 구간이 있으면, 파일을 디스크 처음에 최대한 가깝게 붙여 그 블록들로 옮기고, 원래 블록을 빈 것으로 표시한다.
  • 없으면 파일을 그대로 둔다.

파일을 옮기는 동안에는, 옮겨지는 그 파일이 현재 차지하고 있는 블록도 빈 블록으로 간주한다. 한 번의 패스가 끝나면 일부 파일은 하나의 익스텐트로 줄어들 수 있고, 패스를 더 실행하면 디스크를 더욱 정리할 수 있다.

한편 사용 중이라서 옮길 수 없는 파일도 있다. 이런 파일은 이동 불가(immobile) 로 표시되며 RADDD가 아예 건드리지 않는다. 다만 그 파일이 차지한 블록은 계속 사용 중인 상태로 남는다.

디스크의 크기, 현재 파일 배치, 그리고 실행할 RADDD 패스 횟수가 주어질 때, 최종 배치를 구하라.

입력

첫 줄에는 데이터 세트의 개수를 나타내는 정수 $N$ ($1 \le N \le 100$)이 주어진다. 각 데이터 세트는 다음으로 구성된다.

  • 파일 시스템의 블록 수를 나타내는 정수 $S$ ($2 \le S \le 100000$)가 담긴 한 줄;
  • 파일 개수를 나타내는 정수 $C$ ($1 \le C \le 100$)가 담긴 한 줄;
  • 파일을 설명하는 $C$개의 줄. 각 줄은 NAME TYPE E A-B[ X-Y ...] 형식이며, 여기서:
    • NAME은 데이터 세트 안에서 유일한 식별자로, 소문자 1~16자이다;
    • TYPE은 파일이 이동 불가이면 I, 그렇지 않으면 M이다;
    • E ($1 \le E \le 20$)는 파일이 차지하는 익스텐트의 개수이다;
    • A와 B ($1 \le A, B \le S$)는 각각 첫 번째 익스텐트의 첫 블록과 마지막 블록이다;
    • X와 Y는 있다면 두 번째 익스텐트의 첫 블록과 마지막 블록이며, 이후도 같은 방식이다;
  • 실행할 RADDD 패스 횟수를 나타내는 정수 $P$ ($1 \le P \le 100$)가 담긴 한 줄.

출력

각 데이터 세트마다 DATA SET #k 형식의 줄을 출력한다. 여기서 $k$는 첫 데이터 세트가 1, 두 번째가 2, 이런 식이다. 그다음 RADDD 패스를 모두 실행한 뒤의 파일 배치를, 각 파일이 차지한 첫 블록 번호의 오름차순으로 $C$개의 줄에 출력한다. 형식은 입력과 동일하게 하며, 파일이 여러 익스텐트를 차지하는 경우 각 익스텐트의 첫 블록 번호 오름차순으로 나열한다.