ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1002. Телефонные номера

Problem 1002, why does my program get WA?
Послано Sonny Wibawa Adi 8 мар 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?
Послано Sonny Wibawa Adi 8 мар 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?
Послано Sonny Wibawa Adi 8 мар 2002 14:56
my output for the phone.i7 is:
ape argo ben city book dial end dike harm ink kay