213 - Message Decoding

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

213 - Message Decoding

Post by Whinii F. » Wed Aug 21, 2002 10:13 am

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

Post by Ivan Golubev » Wed Aug 21, 2002 11:02 am

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?

Post by primus » Thu Sep 19, 2002 11:58 pm

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

Post by htl » Thu Jan 16, 2003 6:15 pm

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~~

Post by code# » Mon Jul 05, 2004 5:20 am

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

Post by engsayed » Mon Feb 07, 2005 8:47 pm

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

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

213-(Message Decoding)Runtime error

Post by TISARKER » Mon Feb 27, 2006 6:14 pm

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.
Mr. Arithmetic logic Unit

PEHAT
New poster
Posts: 1
Joined: Wed Aug 09, 2006 3:47 pm

Post by PEHAT » Wed Aug 09, 2006 3:50 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

Post by t_sergiu » Sun Apr 27, 2008 8:34 am

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

Post by brianfry713 » Sat Sep 03, 2011 5:11 am

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

Post by brianfry713 » Sat Sep 03, 2011 5:20 am

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

Post by anacharsis » Mon Jul 13, 2015 12:44 am

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

Post Reply

Return to “Volume 2 (200-299)”