ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1002. Phone Numbers

Problem 1002, why does my program get WA?
Posted by Sonny Wibawa Adi 8 Mar 2002 14:22
I write the code and the output has the same output with the sample
output. Is there a test case for my program, so I can get the bug?

Thank You!

This is the source code:

/* @judge_id: 15467RK 1002 C */
#include <stdio.h>
#include <string.h>

#define MAX 108
#define MAX2 307208
#define MAX3 50000
#define MAX4 51

struct path {
    int id;
    int nextpath;
} path[MAX3];

char number[MAX];
char temp[MAX4];
char dictionary[MAX2];
int pdictionary[MAX3+1];
int tdictionary;
int numlen;
int last;
int bisa[26][100];
int tempbisa[100];
char tempbisaok[100];
int ttempbisa;
int tbisa[26];
int tpath;
int nextpath[100];
int i,j,k,l,m,n;
int min;
int result[MAX];
int tempresult[MAX];
char pre[10][3]={
    {'o','q','z'},
    {'i','j'},
    {'a','b','c'},
    {'d','e','f'},
    {'g','h'},
    {'k','l'},
    {'m','n'},
    {'p','r','s'},
    {'t','u','v'},
    {'w','x','y'}
};
int tpre[10]={
    3,2,3,3,2,2,2,3,3,3
};

void cari (int idx,int tword) {
    int i,j;
    if (min!=MAX && min<=tword) return;
    if (nextpath[idx]!=-1) {
        i=nextpath[idx];
        while (i!=-1) {
            if (pdictionary[path[i].id+1]-pdictionary[path
[i].id]+idx==numlen) {
                if (min==MAX || min>tword) {
                    for (j=0;j<tword-1;j++)
                        result[j]=tempresult
[j];
                    result[tword-1]=path[i].id;
                    min=tword;
                    return;
                }
            } else if (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx<numlen) {
                tempresult[tword-1]=path[i].id;
                cari (pdictionary[path[i].id+1]-
pdictionary[path[i].id]+idx,tword+1);
            }
            i=path[i].nextpath;
        }
    }
}

void main () {
    while (scanf ("%s",number)==1 && number[0]!='-') {
        last=0;
        scanf ("%d",&tdictionary);
        pdictionary[0]=last;
        for (i=0;i<26;i++) tbisa[i]=0;
        numlen=j=strlen (number);
        for (i=0;i<j;i++) {
            for (k=0;k<tpre[number[i]-'0'];k++) {
                l=pre[number[i]-'0'][k]-'a';
                bisa[l][tbisa[l]++]=i;
            }
            nextpath[i]=-1;
        }
        tpath=0;
        for (i=0;i<tdictionary;i++) {
            scanf ("%s",&dictionary[last]);
            ttempbisa=0;
            l=0;
            for (j=0;dictionary[last+j];j++) {
                m=dictionary[last+j]-'a';
                if (ttempbisa || !l) {
                    for (k=0;k<tbisa[m];k++) {
                        if (l) {
                            for
(n=0;n<ttempbisa;n++) {
                                if
(tempbisa[n]==bisa[m][k]) {

    tempbisaok[n]=1;
                                }
                            }
                        } else {
                            tempbisaok
[ttempbisa]=1;
                            tempbisa
[ttempbisa++]=bisa[m][k];
                            l=1;
                        }
                    }
                }
                for (n=ttempbisa-1;n>=0;n--) {
                    if (tempbisaok[n]) {
                        tempbisa[n]++;
                        tempbisaok[n]=0;
                    } else {
                        tempbisa[n]=tempbisa[-
-ttempbisa];
                    }
                }
            }
            for (k=0;k<ttempbisa;k++) {
                if (nextpath[tempbisa[k]-j]==-1) {
                    nextpath[tempbisa[k]-j]=tpath;
                } else {
                    l=nextpath[tempbisa[k]-j];
                    while (path[l].nextpath!=-1)
l=path[l].nextpath;
                    path[l].nextpath=tpath;
                }
                path[tpath].id=i;
                path[tpath].nextpath=-1;
                tpath++;
            }
            last=j+last;
            pdictionary[i+1]=last;
        }
        min=MAX;
        cari (0,1);
        if (min==MAX) puts ("No solution.");
        else {
            for (i=0;i<min;i++) {
                for (j=pdictionary[result
[i]];j<pdictionary[result[i]+1];j++)
                    printf ("%c",dictionary[j]);
                printf (" ");
            }
            puts ("");
        }
    }
}
/* @end_of_source_code */
Re: Problem 1002, why does my program get WA?
Posted by Sonny Wibawa Adi 8 Mar 2002 14:26
I'm sorry. I haven't checked all the messages yet. I will check it
again from the test case at http://www.fi.muni.cz/ceoi/phone/.

Is there a quick way to get messages related with a specific problem
number?

Thanks.
output for phone.o7 has different solution but it is correct, how to break the tie?
Posted by Sonny Wibawa Adi 8 Mar 2002 14:56
my output for the phone.i7 is:
ape argo ben city book dial end dike harm ink kay