IMMEDIATE DECODABILITY

From Progteam

Revision as of 16:37, 15 March 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.


IMMEDIATE DECODABILITY
Problem Number 1056
Sorter: kerry
Source: Unknown
Link: 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];
}
}


Personal tools