HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


14-05-95. 50479 - Bit Compressor

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 14-05-30. 50706 - The most crowd...
• 14-05-40. 50689 - The biggest build...
• 14-05-50. 50414 - Traffic
• 14-05-50. 50421 - Repairing road s...
• 14-05-60. 50371 - Modified Karnaug...
• 14-05-70. 50477 - Character Pyramids
• 14-05-80. 50372 - Number Quadrup...
• 14-05-90. 50549 - k-Nearest Neigh...
• 14-05-95. 50479 - Bit Compressor
• 14-07-10. 50383 - Noisy Mornings
• 14-07-20. 50384 - Permutations revi...
• 14-07-30. 50385 - The 3n + 1 problem
• 14-07-50. 50367 - Bar Codes
• 2013-03-10. 50579 - Pentagonal Nu...
• 2013-03-20. 50589 - The Number of...
• 2013-03-30. 50559 - Prime Factors ...
• 2013-03-40. 50685 - Guest Room U...

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