## 213 - Message Decoding

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### 213 - Message Decoding

I think the problem descript seems alright. but the sample input confuses me..

to look at sample input #1,

TNM AEIOU
0010101100011
1010001001110110011
11000

description says that all carriage returns are to be ignored, so I concatenated all the binary strings together (I didn't in my program, I read it line by line).

So it looks like

TNM AEIOU
0010101100011101000100111011001111000

Seems alright.. and to remove that finish identifier 000 from the end, we see

TNM AEIOU
0010101100011101000100111011001111

The first 3 digits represent 1, so the first segment would be

001 0 1

alright? Of course 0 represents 'T'. Satisfied with that

The next 3 digits represent 3 (011), so the next segment would be

011 000 111 (000 represents 'A')

The next segments give out a problem. The length digits represent 2 (010), alright? and the segment would be

010 00 10

why the last part, the 1's part isn't complete? I was confused with this for hours.. anybody help me :'(
JongMan @ Yonsei

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
The next segments give out a problem. The length digits represent 2 (010), alright? and the segment would be

010 00 10

why the last part, the 1's part isn't complete? I was confused with this for hours.. anybody help me :'(
You're need to process bits until you're got the code consisting only of ones. So sequence will be

010(length == 2) 00(N) 10(space) 01(M) 11(sequence finished) 011(length == 3) 000(E) 111(sequence finished) 000(end of message)

primus
New poster
Posts: 1
Joined: Thu Sep 19, 2002 11:54 pm

### 213 Erroneous specification?

In the specification of problem 213, it says that "if two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2)". Then in the listing of the keys it is printed: ",1011,1110". The last time I checked, 1110 + 1 is not 1110. The correct sequence should be "1101,1110"

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 213

This should be a simple problem. But I still get WA. According to the description, the max number of 'key' should be 247. But in fact the number is bigger than it. Can someone help figure them out?
[c]
#include<stdio.h>
void main(void)
{
int x,pow[7]={2,4,8,16,32,64,128},len,k,y;
char db[400],c,out[1000];
while(gets(db)!=NULL)
{
y=0;
while(1)
{
for(x=0,len=0;x<3;)
{
c=getchar();
if(c=='0' || c=='1')
{
x++;
len=len*2+c-'0';
}
}
if(!len)
break;
while(1)
{
for(x=0,k=0;x<len;)
{
c=getchar();
if(c=='0' || c=='1')
{
x++;
k=k*2+c-'0';
}
}
if(k==pow[len-1]-1)
break;
out[y++]=db[pow[len-1]-len+k-1];
}
}
for(x=0;x<y;x++)
printf("%c",out[x]);
printf("\n");
c=getchar();
}
}
[/c]

code#
New poster
Posts: 2
Joined: Sun Jul 04, 2004 3:04 am

### 213 Sample Input Plz~~

I think that my source is right..-_-;;

but I recieve WA always..=_=;;

so I want seek the part that I think wrong.

I want other sample input & output..

Help Plz~+_+

engsayed
New poster
Posts: 1
Joined: Mon Feb 07, 2005 6:04 pm

### prob 213 plz help

hi
in problem 213
what is the maximum number of datasets?
and what is the maximum number of characters in the decoded message?
thank you
bye[/list]

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Contact:

### 213-(Message Decoding)Runtime error

I am getting RE.
I could not undersatnd following lines.
The encoded message contains only 0's and 1's and possibly carriage returns, which are to be ignored.
Carriage returns may appear anywhere within the message part. They are not to be considered as part of the message.
Mr. Arithmetic logic Unit

PEHAT
New poster
Posts: 1
Joined: Wed Aug 09, 2006 3:47 pm
It is not the only error about that problem.
If you look at the sample input:
\$#**\
010 00 00 101101100011100001000
i.e.:
010 00 00 10 11
011 000 111
000? - it must be the end of message.
The correct variant is 001
001 0 1
000 - real end.

t_sergiu
New poster
Posts: 12
Joined: Sun Mar 02, 2008 6:18 am

### Re: 213

I'd like some sample cases with this problem as well as I think I my algorithm works but am getting WA.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: prob 213 plz help

To answer both your questions, my AC program considered the number of datasets and the length of the decoded message unlimited.

The problem states that the max length of the keys in the header is 7. That gives a total of (2^n)-1 for n=1 to 7, or 1+3+7+15+31+63+127=247 max characters in the header.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 213

htl, I glanced at your code and noticed that your out array size is limited to 1000, my AC program considered the number of datasets and the length of the decoded message unlimited. Rry rewriting your code so that the output is printed as you decode it instead of after all the decoding.

The problem states that the max length of the keys in the header is 7. That gives a total of (2^n)-1 for n=1 to 7, or 1+3+7+15+31+63+127=247 max characters in the header. I agree with you there, but I don't know why you're convinced it's larger than that.
Check input and AC output for thousands of problems on uDebug!

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

### Re: 213 - Message Decoding

In:

Code: Select all

``````ABCDEFG
0010101000011011011000001010000
AAAAAAA
0010101000011011011000001010000
ABCDEFG
001000000000101001010101000
ABCDEFG
001000
00000
0101001010
10111000
``````
AC out:

Code: Select all

``````ABCDEFG
AAAAAAA
AAAAAAAAACCCC
AAAAAAAAACCCC
``````