Friday, April 24, 2015

UVa - 644 - Immediate Decodability

#include <bits/stdc++.h>
using namespace std;

struct data{
    int sze;
    string code;
}ar[13];

bool cmp(data a, data b){
    if(a.sze != b.sze)return a.sze < b.sze;
    return a.code < b.code;
}

int main(){
    int sz[13], cs = 0;
    string temp, inn;
    while(cin >> inn){
        int sz = 0, flag = 0;
        ar[sz].code = inn;
        ar[sz].sze = inn.size();
        sz += 1;
        while(cin >> inn){
            if(inn == "9")break;
            ar[sz].code = inn;
            ar[sz].sze = inn.size();
            sz += 1;
        }
        sort(ar, ar+sz, cmp);
        for(int i = 0; i < sz; i++){
            for(int j = i+1; j < sz; j++){
                temp.clear();
                if((ar[i].sze == ar[j].sze) && (ar[i].code == ar[j].code)){
                    flag = 1;break;
                }
                for(int k = 0; k < ar[i].sze; k++)temp.push_back(ar[j].code[k]);
                if(temp == ar[i].code){
                    flag = 1; break;
                }
            }
        }
        if(flag)cout << "Set " << ++cs << " is not immediately decodable" << endl;
        else cout << "Set " << ++cs << " is immediately decodable" << endl;
        for(int i = 0; i < sz; i++)ar[i].code.clear();
    }
    return 0;
}

No comments:

Post a Comment