ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Data Structures > задача:


50479 - Bit Compressor

Гость
• Вопросы к жюри (1)

Задачи сборника

• 50367 - Bar Codes
• 50549 - k-Nearest Neighbours (kNN)
• 50697 - Base Stations
• 50479 - Bit Compressor
• 50383 - Noisy Mornings
• 50486 - Problems and Programmers
• 50695 - Longest link between neurons
• 50677 - The Cottage
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50700 - Candidates for the Mayor
• 50415 - The Scientist

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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