Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Osman Ay.
Bit Compressor
{ACM ICPC World Finals 2006, Osman Ay}
Problem Description:
The aim of data compression is to reduce
redundancy in stored or communicated data,
thus to increase effective data density.
Data compression has important applications
in the areas of file storage and distributed
systems.
Any kind of data is transferred from a source
node to a destination node in bits on a network
or on the Internet environment. Compression
any binary message, just before sending it,
will provide a faster data transfer. The
following method can be used to compress any
binary message:
Replace the consecutive 1s with the number of
those 1s if it shortens the length of the message.
For example, the compressed form of the data
11111111001001111111111111110011 becomes
10000010011110011. The original data is 32
bit-length and the compressed data is 17
bit-length.
The drawback of this method is that sometimes
the uncompressing process yields more than one
result as the original message. In such a case,
it can be impossible to obtain the original message.
Make a program that determines if the original
message can be obtained from the compressed data
when the length of the original message (L), the
number of the 1s in the original message (N) and
the compressed data is given. The original message
is not longer than 16 Kbytes and the compressed
data is not longer than 40 bits.
Input specification
The input file contains several test cases.
Each test case has two lines. The first line
contains L and N and the second line contains
the compressed data. The input file ends with
two zeros in the last line.
Output specification
Show each test case output on a separate line
with a message "YES", "NO" or "NOT UNIQUE". YES
means the original message can be obtained, NO
means the compressed data has been corrupted and
the original message can not be obtained, NOT
UNIQUE means more than one message can be
obtained as the original message.
Sample Input I |
Sample Output I |
32 26
10000010011110011
13 10
11011011011
10 10
11111
19 15
110111011011011
0 0
|
YES
NOT UNIQUE
NO
YES
|
Для отправки решений необходимо выполнить вход.
|