HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Exhaustive search & Backtracking > problem:


50479 - Bit Compressor

Guest
• Review clarifications (1)

Section problems

• 50716 - All Palindromes
• 50714 - The knight
• 50713 - Castle and the girls
• 50710 - Permutations
• 50709 - k-ary Strings
• 50708 - Binary Strings
• 50996 - Checkers - the shortest path
• Check-Mate
• 50479 - Bit Compressor
• 50486 - Problems and Programmers
• 50712 - Moon algebra
• 50717 - Hurdle Jumping
• 50840 - Tanker trucks
• 50490 - Across the River
• 50828 - Arranging Time Table
• 51067 - Jumping frog
• 51142 - Jump Min Value

Feedback

If you notice incorrect translations in Contester, please let author know.

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


Для отправки решений необходимо выполнить вход.

www.contester.ru