644 - Immediate Decodability

All about problems in Volume 6. 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
deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

644 - Immediate Decodability

Post by deddy one » Sat Jan 18, 2003 1:33 pm

I'm getting WA in this problem
what's wrong
is it my function checking?????


[c]

cut

[/c]
Last edited by deddy one on Tue Apr 29, 2003 11:47 am, edited 1 time in total.

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Thu Jan 23, 2003 1:47 pm

Read the problem carefully...

Your output "decodeable" should be "decodable", right ? :lol:

Regards,
Angga888

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Jan 23, 2003 4:01 pm

oh my god, how can I be this stupid :oops: :oops: :oops: :oops:


thx a lot angga
I get it acc now :D :D

you're a life saver

644 - HELPMEPLEASE
New poster
Posts: 1
Joined: Tue Apr 22, 2003 2:14 pm
Contact:

644

Post by 644 - HELPMEPLEASE » Tue Apr 22, 2003 2:23 pm

Help me please. I don't know what is wrong. I HATE THIS JUDGE!!! :evil:
Maybe u got some source.
[pascal]
program decoding;
var
a:array[1..9] of string[10];
i,j,k,l:byte;
b:string[10];
res:boolean;
function equ(a1,a2:string):boolean;
var i:byte;
res:boolean;
begin
res:=true;
for i:=1 to length(a2) do
res:=res and (a1=a2);
equ:=res;
end;
procedure mainloop;
var w1,w2:byte;
begin
while (k<i) and not(res) do
begin
inc(k);
j:=1;
while (j<=i) and not(res) do
begin
w1:=length(a[k]);
w2:=length(a[j]);
if (j<>k) and (w1<=w2) then
res:=res or equ(a[j],a[k]);
inc(j);
end;
end;
end;
begin
i:=0; l:=0;
while not eof(input) do
begin
readln(input,b);
if b='9' then
begin
k:=0; inc(l);
res:=false;
mainloop;
str(l,b);
if not(res) then
writeln(output,'Set '+b+' is immediately decodable')
else
writeln(output,'Set '+b+' is not immediately decodable');
i:=0;
end
else
begin
inc(i);
a:=b;
end;
end;
end.[/pascal]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed May 07, 2003 12:11 pm

Becareful the 'enter' can be appear everywhere.
I solve this problem by using function getchar, and if the character not '0' or '1', I ignore it.
The hardest of this problem is parsing input, and it always cause WA.

Consider the input can be like this:
0
1
1
0
0
010
00
0
0
9

Hope this helps. :lol:

jihajdu
New poster
Posts: 2
Joined: Sat Nov 05, 2005 12:04 pm
Location: Budapest, Hungary

644 - WA

Post by jihajdu » Sun Dec 11, 2005 9:03 am

Hi,

could someone please give me some test inputs and outputs for problem 644? I've tried lots of tests and my algorithm seems correct but judge gave me WA. Are the constraints of the problem correct? (2-8 codes in each set with 1-10 bits) Thanks in advance!

Jeno

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 8:53 pm

Just check the following test case...

Input:

Code: Select all

01
10
0010
001
9
Output:

Code: Select all

Set 1 is not immediately decodable
Hope it works.
Ami ekhono shopno dekhi...
HomePage

jihajdu
New poster
Posts: 2
Joined: Sat Nov 05, 2005 12:04 pm
Location: Budapest, Hungary

Post by jihajdu » Tue Jan 03, 2006 9:16 am

Thanks for your test case, it helped!
Cases like 001 after 0010 weren't handled correctly, only 0010 after 001. Now I've got AC. :)

Jeno

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

644 - Immediate Decodability ..Getting WA

Post by kangroo » Fri Sep 12, 2008 3:38 pm

need help...!!!

Code: Select all

#define foriz(i,n) for( i = 0 ; i < n ; i ++ ) 

bool immediately_decodable ( vecs cd )
{
 sort( cd.begin() , cd.end() );
 int i , j;
 foriz ( i , sz(cd) ) 
 {
  foriz ( j , sz(cd) )
  {
   if ( i != j && sz(cd[j]) >= sz(cd[i]) )
   {
    string x = cd[j].substr ( 0 , sz(cd[i]) );
    if ( x == cd[i] )
     return false;
   }
  }
 }
 return true;
}

int main ()
{
 int cas = 1;
 string s;
 while ( !feof(stdin) )
 {
  vecs codes;
  while ( true )
  {
   cin >> s;
   if ( s == "9" ) break;
   else codes.pb (s);
  }

  if ( immediately_decodable ( codes ) )
   printf ( "Set %d is immediately decodable\n" , cas ++ );
  else
   printf ( "Set %d is not immediately decodable\n" , cas ++ );
  codes.clear();
 }
 return 0;
}

anyone pls help me!!
thanks...

tanvir_cse
New poster
Posts: 9
Joined: Wed Jul 09, 2008 10:12 pm

644 - Immediate Decodability : TERMINATION CONDITION

Post by tanvir_cse » Fri Dec 05, 2008 5:59 am

What is the termination condition of this problem?
No, such type of terination condition.I am getting TLE because of this.Pls, inform :oops:

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 644 - Immediate Decodability : TERMINATION CONDITION

Post by saiful_sust » Thu May 28, 2009 9:32 pm

Hello tanvir_cse

U have to read the input upto end of file.
and when u get 9 u will print result

take input like that
while(scanf(" %s", code[num]) == 1)
{
while(1)
{
if (code[num][0] == '9') break;
scanf(" %s", code[++num]);
}
//some code here;
}

fahim_xubayer
New poster
Posts: 5
Joined: Wed Sep 23, 2009 8:57 am

Re: 644 - Immediate Decodability

Post by fahim_xubayer » Wed Oct 28, 2009 11:15 pm

getting WA.can anyone please help?

Code: Select all

#include<stdio.h>
#include<string.h>
int main(){

  int a,b=0,d,e,f,x,y,z,bi[9][10],l,len[10],zz=1,aa,p,q;
  char c,m[11];
  while(gets(m)){
    
    l=strlen(m);
    len[b]=l;
    
    for(a=0;a<l;a++)
    bi[b][a]=m[a]-48;
    b++;
    if(m[0]!='9')
    continue;
    
    
    p=0;q=0;
  
    for(e=0;e<b;e++){
      for(f=e+1;f<b;f++){
       if(len[e]<len[f]){
          for(a=0;a<len[e];a++){
            if(bi[e][a]!=bi[f][a])
            break;
      
          }
        }
        if(a==len[e]){
   
        p++;
          break;
        }
      }
      if(a==len[e])
      break;
    }
    for(e=b-1;e>=0;e--){
      for(f=e-1;f>=0;f--){
       if(len[e]<len[f]){
         
          for(aa=0;aa<len[e];aa++){
            if(bi[e][aa]!=bi[f][aa])
            break;
          }
        }
        if(aa==len[e]){
    
        q++;
          break;
        }
      }
      if(aa==len[e])
      break;
    }
    if((p>0)||(q>0)){
      p=0;q=0;
      printf("Set %d is not immediately decodable\n",zz);
      zz++;
      b=0;
      continue;
    }
      
    
    if((p==0)&&(q==0)){
    printf("Set %d is immediately decodable\n",zz);
    zz++;
    b=0;
  }
  }
  return 0;
}
    
    
      
      
      
      
    
    

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 644 - Immediate Decodability

Post by uDebug » Mon Feb 24, 2014 9:47 am

fahim_xubayer wrote:getting WA.can anyone please help?
Try the following input:

Code: Select all

01
01
9
AC Output:

Code: Select all

Set 1 is not immediately decodable
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re:

Post by uDebug » Mon Feb 24, 2014 9:48 am

Jan wrote:Just check the following test case...
Thanks for sharing this great test case!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 6 (600-699)”