|Submit||All submissions||Best solutions||Back to list|
HS12DFRG - Defragmentation
A new file system on a disk partition contains only a few small internal structures and one contiguous block of empty space. Once you start to use the system and fill the space with data, creating new files, deleting, truncating, and extending them, this orderly empty space becomes more and more fragmented and the performance of the system drops. This is often called system ageing.
To prevent system ageing and the performance decrease, one might want to defragment the disk surface. You are probably aware of some tools to do so. In this task you will be asked to deal with a simplified version of some of the optimization problems you would meet while constructing such software.
Given the simplified file structure description, try to defragment it using a limited number of copy operations.
In the first line of input you are given two numbers: n - the number of files in the system and m – the number of disk memory allocation blocks.
In the successive n lines, the description of files follows. Each file is described by two strings: FileName (alphanumeric ASCII string, four characters long) and StartingBlock (a hexadecimal four-digit number).
Next, there is an empty line and in the successive m lines, the descriptions of the blocks follow. Each block is described by two strings: BlockData (alphanumeric ASCII string, four characters long) and NextBlock (a hexadecimal four-digit number). The first character of BlockData is either 'U' denoting a used block or 'E' for an empty block. The next three characters of BlockData describe either the essential file data, or just rubbish in the case of empty blocks.
NextBlock redirects to the next block of the file. NextBlock equal to FFFF indicates the last block in the file.
Output one word: NOTHING if you do not want to solve a given test.
Otherwise, first output c – the number of copy operations and in the c following lines, output the appropriate description of the operations. Every copy operation is of the form: Source Destination Predecessor'sType Predecessor.
Source indicates the number of a source block. Destination is the number of a destination block (the destination block must be empty). Predecessor'sType is one character, either 'F' for a file table entry, or 'B' for a block. Predecessor is either the file name or the block number.
Observe that copying of a block affects not only the considered block but also the preceeding block (or the file table in the case of the first block in the file).
At the end of your output print an empty line and the disk structure in the same format as that given in the input.
Let us consider two consecutive blocks of the same file, say i is the block number of the first block and j is the position of the next block (NextBlock for i is j). If j is not equal to i+1, the situation is called a jump (the file is fragmented at this point).
The score awarded to your program for a given test is the difference between the Initial number of jumps and the final number of jump, times 10, minus the number of copy operations: 10*(InitJ-FinalJ)-c.
The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.
An attempt to perform an incorrect operation, such as copying non-existent blocks, using a non-empty block as a destination, inconsistent or invalid disk structure will be judged as Wrong Answer.
Input: 3 12 F001 0003 3aaL 0001 GGhu 000A EXa3 34EA UNDO 0002 UNDO FFFF URea 0007 Eaae 0000 Uool FFFF E232 0000 Uson 0009 Eeee FE43 Uing 000B UYes FFFF UIsC 0005 Output: 4 0007 0004 B 0003 0005 0007 B 000B 0009 0005 B 0004 000B 0006 B 0005 3 12 F001 0003 3aaL 0001 GGhu 000A EXa3 34EA UNDO 0002 UNDO FFFF URea 0004 Uson 0005 Uing 0006 UIsC 0007 Uool FFFF Eeee FE43 Eing 000B UYes FFFF EIsC 0007 Scoring: 36 Scoring explanation The initial number of jumps is: 4 The final number of jumps is: 0 The number of copy operations is: 4 The score is (4-0)*10 - 4 = 36
Input data sizes
t n m u l 1 4 10 8 2s 2 4 100 25 2s 3 26 600 400 2s 4 87 1140 175 2s 5 100 7300 2890 2s 6 110 7310 5890 5s 7 156 690 410 5s 8 31 580 430 5s 9 6 100 43 5s 10 5 18 16 5s t - test set number n - the number of files m - the number of blocks u - the number of used blocks l - time limit
- Until the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
- For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full test sets (all earlier solutions will be rejudged).
- Please do not submit more than 100 times to this problem (all submissions starting with the 101st will be ignored).
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET|
|Resource:||High School Programming League|