213 - Message Decoding

[Whinii F.]

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 :'(

[Ivan Golubev]

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]

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]

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#]

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]

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]

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.

Please clarify me about above lines with example.

[PEHAT]

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]

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

[brianfry713]

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.

[brianfry713]

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.

[anacharsis]

Possibly helpful test cases

In:

Code: Select all

ABCDEFG
0010101000011011011000001010000
AAAAAAA
0010101000011011011000001010000
ABCDEFG
001000000000101001010101000
ABCDEFG
001000
00000
0101001010
10111000

AC out:

Code: Select all

ABCDEFG
AAAAAAA
AAAAAAAAACCCC
AAAAAAAAACCCC