A8499. Defragmentation
编程题
普及/提高-
知识点
题目描述
The first line contains two integers $n$ and $m$ ( $1<=n,m<=200$ ) — the number of clusters and the number of files, correspondingly. Next $m$ lines contain descriptions of the files. The first number in the line is $n_{i}$ ( $n_{i}>=1$ ), the number of clusters occupied by the $i$ -th file. Then follow $n_{i}$ numbers $a_{i,1}$ , $a_{i,2}$ , ..., $a_{i,ni}$ ( $1<=a_{i,j}<=n$ ). It is guaranteed that each cluster number occurs not more than once and , that is, there exists at least one unused cluster. Numbers on each line are separated by spaces.
输入格式
In the first line print a single integer $k$ ( $0<=k<=2n$ ) — the number of operations needed to defragment the disk. Next $k$ lines should contain the operations' descriptions as " $i$ $j$ " (copy the contents of the cluster number $i$ to the cluster number $j$ ).
输出格式
Let's say that a disk consists of $8$ clusters and contains two files. The first file occupies two clusters and the second file occupies three clusters. Let's look at examples of correct and incorrect positions of files after defragmentation.
Example 2: each file must occupy a contiguous area of memory.
Example 3: the order of files to each other is not important, at first the second file can be written, and then — the first one.
Example 4: violating the order of file fragments to each other is not allowed.
Example 5: unused clusters should be located at the end, and in this example the unused clusters are $3$ , $7$ , $8$ .
Example 2: each file must occupy a contiguous area of memory.
Example 3: the order of files to each other is not important, at first the second file can be written, and then — the first one.
Example 4: violating the order of file fragments to each other is not allowed.
Example 5: unused clusters should be located at the end, and in this example the unused clusters are $3$ , $7$ , $8$ .
输入输出样例
输入 #1
7 2 2 1 2 3 3 4 5
输出 #1
0
输入 #2
7 2 2 1 3 3 2 4 5
输出 #2
3 2 6 3 2 6 3
说明/提示
Let's say that a disk consists of $8$ clusters and contains two files. The first file occupies two clusters and the second file occupies three clusters. Let's look at examples of correct and incorrect positions of files after defragmentation.
Example 2: each file must occupy a contiguous area of memory.
Example 3: the order of files to each other is not important, at first the second file can be written, and then — the first one.
Example 4: violating the order of file fragments to each other is not allowed.
Example 5: unused clusters should be located at the end, and in this example the unused clusters are $3$ , $7$ , $8$ .
Example 2: each file must occupy a contiguous area of memory.
Example 3: the order of files to each other is not important, at first the second file can be written, and then — the first one.
Example 4: violating the order of file fragments to each other is not allowed.
Example 5: unused clusters should be located at the end, and in this example the unused clusters are $3$ , $7$ , $8$ .