Polish version    English version  
  History of OI -> II OI 1994/1995 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
Stage III - results
Stage I - results
Problems
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: OPT
Author: Tomasz Śmigielski, Piotr Krysiuk
Disk Optimization

I stage contest  

A disk consists of N sectors numbered successively from 1 to N. Any nonempty sequence of sectors having consecutive numbers is called a block. A length of a block is the number of sectors in the block. Blocks are separate if they have no common sector.

There are files written on a disk. A single file may be written on many sectors, which need not form a single block. To reconstruct a file correctly one needs to read those sectors in right order. This sequence of sectors determines a sequence of separate blocks - each of them contains one or more sectors. Sectors inside each block are read in order of their numbers.

A description of a file distribution on a disk is a sequence of pairs of positive integers. Each of these pairs comprises the number of the starting sector of a block and the length of the block.

Example

The sequence of pairs:
7 3
2 1
5 2
informs that the contents of the file ought to be read successively from the sectors numbered: 7, 8, 9, next: 2, and next: 5, 6.

Each sector on a disk may be either free or there may be written a part of only one file (or one whole file).

Each file has a unique ID - a positive integer in the range of 1 to P, where P is the number of files on the disk.

A disk is optimized when:

  • each file is stored in one block (in consecutive sectors),
  • a file with a smaller ID occupies sectors of lower numbers than every file with a greater ID,
  • every free sector has a greater number than every occupied sector.

One may perform the following operations on a disk:

  • copying the contents of a block to a separate block of the same length,
  • swapping the contents of two separate blocks of the same length.

Copying a block of length t lasts t microseconds. Swapping contents of two blocks of length t lasts 2*t microseconds.

The instruction to copy a block has the form:
K start new_start length
The instruction to swap blocks has the form:
Z start1 start2 length
K and Z are short forms of "kopiowanie" ("copying") and "zamiana" ("swapping"), and start is the number of the first sector of a block.

Task

Write a program that:
  • reads from the text file OPT.IN the number of sectors, the number of files and descriptions of their distributions on the disk,
  • examines whether the disk is optimized.
    If so, the program writes only one word NIC ("nothing") to the file OPT.OUT.
    If not, the program generates an appropriate sequence of instructions that optimizes the disk in the shortest time possible (the number of instructions is not important; only the collective time to perform all the instructions signifies); next the program writes the sequence of instructions to the text file OPT.OUT.

Input

In the first line of the data file OPT.IN there are written two positive integers: the number of sectors on the disk N, not greater than 10000, and the number of files P.

Next in the successive lines there are descriptions of file distributions on the disk.

Each file description contains two numbers in the first line: the file's ID from the range of 1 to P and a positive number denoting the number of separate blocks the file is written in. In the next lines there is the description of the file distribution in a form of an appropriate sequence of pairs of positive integers, one pair per line.

The numbers in lines are separated by single spaces.

The data in the file OPT.IN are written correctly and your program need not verify that.

Output

The file OPT.OUT is to contain:
  • either only one word NIC, when the disk is already optimized,
  • or a sequence of instructions - one per line. Each instruction has to be written conforming to the format given above: first a capital letter K or Z, a single space, then three positive integers separated by single spaces.

Example

For the file OPT.IN:
200 2
2 2
51 10
41 10
1 2
71 20
11 20
the file OPT.OUT may have the form:
K 21 31 10
K 11 21 10
K 71 1 20
Z 41 51 10

Your program should look for the file OPT.IN in the current directory and create the file OPT.OUT also in the current directory. The source file containing the program written by you should be named OPT.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file OPT.EXE.




Print friendly version