# IMMEDIATE DECODABILITY

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by kerry.

 Sorter: kerry Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1056

IMMEDIATE DECODABILITY is problem number 1056 on the Peking University ACM site.

Here's the code. Finally, an easy problem! Accepted by PKU. -Kerry

```
// Rationale: read in input, sort by length, then compare short sequences to the beginning of longer
// sequences. If any match, then the code is not decodable.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct code {
char length;
char code[12];
};

int main() {
int i=0, j=0, tmp, done=0, decodable, count=1;
struct code codes[9];
char end='a',a=0;

while(end) {
decodable=1;                     // Initially assume decodability.
for(j=0;j<9;j++) {               // Initialize that will recieve input
codes[j].length=0;
for(i=0;i<12;i++)
codes[j].code[i]=0;
}
i=0;
j=1;
a=getchar();                    //This bit is a little awkward, but checks for EOF on the
if (a==EOF)                     // first line of a block of input
return;
codes[0].code[0]=a;
while (a!= '9') {                    // Read input into codes[]
if ((a=getchar())=='\n') {
codes[i].code[j]=0;
codes[i].length=strlen(&(codes[i].code[0]));
i++;
j=0;
continue;
}

else
codes[i].code[j++]=a;
}
getchar();   //chomp newline
i=0;
while (done<9) {           // Sort by length. Uses empty codes[8] as temp storage during swap
if(i<9 &&(codes[i].length>codes[i+1].length)) {
codes[8]=codes[i];
codes[i]=codes[i+1];
codes[++i]=codes[8];
}
done++;
}

for (i=0;i<9;i++) {
if (codes[i].length!=0) {
for (j=0;j<9;j++) {  // Now check if short codes == beginning of long codes
if(i==j)
continue;
if (!strncmp(&codes[i].code[0], &codes[j].code[0], codes[i].length))
decodable=0;
}
}
}
if (decodable)
printf("Set %d is immediately decodable\n", count);
else
printf("Set %d is not immediately decodable\n", count);
count++;
end=codes[0].code[0];
}
}

```