Modern writers do not use pens to write books. They enter the text directly on to the home PCs using MS Word and edit the text when necessary.
After entering the text for a new book, a famous novelist desires to have a major rearrangement of the text he has prepared. He has identified passages in the text and numbered
these passages. However the passages are not in proper equence. He wants to use the minimum number of cut and paste operations of MS Word to edit the text and put the passages
in proper order. He may do the operation either with one passage or with a number of passages occurring in a sequence. He needs a program for this purpose.
The following example illustrates his problem. In order to edit the text containing 6 passages in the sequence P2, P4, P1, P5, P3, P6 so that the passages appear in the text in the
proper sequence viz., P1, P2, P3, P4, P5, P6 he needs at least 2 cut and paste operations:
The input may contain multiple test cases.
For each test case, the first line contains two integers, the case number c and the total number n of passages.
For simplicity, passages are represented by integers 1, 2, ??n. The input sequence of passages is given in n lines, each line containing one integer in the order in which the passages
appear in the text before editing.
The entire input set terminates with an input 0 for c.
For each test case in the input, print the test case number c and the total number k of cut.
Print a blank line between outputs of two test cases.
1 6 2 4 1 5 3 6 2 15 12 6 7 2 3 4 9 10 11 1 5 8 13 14 15 0
1 2 2 4
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|