139 - Telephone Tangles

[ar2rd]

I'm doing that problem for a quite long time, and I'm desparate now. Could anybody supply some test cases that could brake that code:

Code: Select all

// Telephone Tangles - acm.uva.es/p/v1/139.html
// by Artur Dmowski
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXL 10001
#define REP(i,n) for(int i=0,tn=n; i<tn; i++)
using namespace std;

// DATA
char *name[MAXL],*code[MAXL],*dial;
double cost[MAXL];
int n=0,i=0,t,c;

// FUNC
bool prefix( char *p, char*s ) {
    int k = strlen(p);
    REP(c,k) if( p[c] != s[c] ) return 0;
    k = strlen(s)-k;
    return k>=4&&(s[1]=='0'?k<=10:k<=7);
}
int search( char *num ) {
    int k = n, l = -1, d;
    if( num[0] != '0' ) return n+1;
    REP(a,n) if( prefix(code[a],num) ) d=strlen(code[a]), (l<d ? l=d,k=a : l=l);
    return k;
}
// MAIN
int main() {
#ifndef ONLINE_JUDGE
    freopen("139.in", "r", stdin);
#endif
    memset( cost, -1, sizeof(cost) );
    memset( name,  0, sizeof(name) );

    REP(a,MAXL) name[a] = (char*) malloc(30), code[a] = (char*) malloc(10);
    dial = (char*) malloc(50);

    while( scanf("%s ",code[n]) && strcmp(code[n],"000000") ) {
	gets( name[n] ); i=0; 
	while( name[n][i] != '$' ) i++;
	name[n][i] = '\0';
	sscanf(name[n]+i+1,"%llf", &cost[n]);
	cost[n] /= 100.0;
	n++;
    }
    name[n  ] = "Unknown";
    name[n+1] = "Local", cost[n+1] = 0.00;

    while( scanf("%s %d\n",dial,&t) && strcmp(dial,"#") ) { 
	i = search( dial ), c = strlen(code[i])*(i!=n+1);
	printf("%s %s", dial, name[i]);
	if( i != n ) printf(" %s", dial+c);
	printf(" %d", t);
	if( i != n ) printf(" %.2f %.2f\n",cost[i],t*cost[i]);
	else printf(" %.2f\n",-1.00);
    }
    return 0;
}

Thanks in advance. I'm grateful for any help.

[Ruberik]

"The second part contains the log and will consist of a series of lines, one for each call"

This is incorrect. Each call may be broken up over multiple lines, as per the following input:

088925 Broadwood$81
03 Arrowtown$38
0061 Australia$140
000000
031526 22
0061853279 3
0889256287213 122
779760
1
002832769 5
#

...which is identical in output to the sample input. I had WA code, changed it so that I used cin >> number >> minutes instead of using getline, and got Accepted.

Well, I guess the 11% success rate should have been a hint that quality-control wasn't so high on that one. :)

[Yu Fan]

I've read some posts on the board and test some IO. but still the judge reply me a lot of WA...
someone says that the problem has some tricky point but i can't find it, could anyone help me examine my code??
thanks in advance

Code: Select all

#include <stdio.h>
#include <string.h>
char name[3000][100];
char num[3000][100];
int n = 0;
int price[3000];
int main() {
    char q[100], q2[100];
    int i, j, d;
    while (gets(q) && strncmp(q, "000000", 6)) {
        sscanf(q, "%s", &num[n]);
//        printf("%s\n", num[n]);
        for (i = 0; q[i] != '$'; i++);
        strncpy(name[n], q + strlen(num[n]) + 1, i - strlen(num[n]) - 1);
        sscanf(&q[i + 1], "%d", &price[n++]);
    }

    while (scanf("%s", &q) && strcmp(q, "#")) {
        scanf("%d", &d);
        if (strlen(q) > 15)
            goto end;
        if (q[0] != '0') {
            printf("%-16s%-26s%9s%5d  0.00   0.00\n", q, "Local", q, d, 0);
            continue;
        }
        for (i = 0; i < n && strncmp(num[i], q, strlen(num[i])); i++);
        if (i < n) {
            j = strlen(q) - strlen(num[i]);
            if (q[1] == '0' && (j < 4 || j > 10))
                i = n;
            if (q[1] != '0' && (j < 4 || j > 7))
                i = n;
        }
        if (i < n)
            printf("%-16s%-26s%9s%5d%6.2lf%7.2lf\n", q, name[i], &q[strlen(num[i])], d, (double)price[i] / 100, (double)price[i] / 100 * d);
        else
end:        printf("%-16s%-26s%14d%13s\n", q, "Unknown", d, "-1.00");
    }
    return 0;
}

[rickyliu]

You may have solved it. If not, try this:

Code: Select all

0061 Australia$140
00 Los Angeles$10
000000
0061234 5
00612345 6
#

My AC (though PE) program gave the following output:

Code: Select all

0061234         Los Angeles                   61234    5  0.10   0.50
00612345        Australia                      2345    6  1.40   8.40

This is yours:

Code: Select all

0061234         Unknown                                5        -1.00
00612345        Australia                      2345    6  1.40   8.40

Hope this helps.

[rickyliu]

According to the problem statistics, there are 575 got PE but only 162 got AC! This problem must have a very tricky input that I cannot figure it out. I guessed it might be the locality names. I have tried zero length, leading spaces and spaces in between. I also verified with the output statements with those posted to the board. Nothing special differences were found. Since the judge considers PE as not accepted now, would anyone gives some hints on this?

Edited (add): For IDD with 3 country codes, 10 subscriber's number and locality name with 25 characters, the output will be messed up in the 2 fields: locality name and subscriber's number according to the sample output layout. Is it ok not to have any spaces between them?

It seems to me that it is an error (or at least unclear) in the report layout.

Many thanks.

Ricky Liu

[rickyliu]

I just found the problem and got AC.
For those got PE, please consider the case where the Local phone numbers with more than 10 digits.

[Yu Fan]

Although i haven't try it yet but thank you very much!!

[rio]

I tried your input rickyliu, but my code says the numbers is ambiguous.

I think second number 00612345 could be taken two ways.

00 + 61(country code) + 2345 -> Austrailia
0 + 0(area code) + 612345 -> Los Angeles

Am I right? Or just misunderstanding the proglem statement ?
Anyway, keep getting WA..

[rickyliu]

Am I right?

Yes, you are right. It is ambiguous. Shouldn't use it for the testing input.

Here are the other input/output for your reference:
Input:

Code: Select all

088925 Broadwood0000000baaaaaaad$81
03  Arrowtown $38
01 $24
0061 Australia$140
00852 Hong Kong.012345678901234$1111
00 Los Angelos$10
000000
031526        22
0889256287213   122
008520123456789   64
779760	 1
  002832769   	 5
001234 1   
0123456 3
0123 4
00134 5
00123456789012 9
0061234 600
0061853279  300
00611234567890 700
006112345678901 800
123456789 2
123456789012345 4
#

Output:

Code: Select all

031526           Arrowtown                     1526   22  0.38   8.36
0889256287213   Broadwood0000000baaaaaaad   6287213  122  0.81  98.82
008520123456789 Hong Kong.0123456789012340123456789   64 11.11 711.04
779760          Local                        779760    1  0.00   0.00
002832769       Los Angelos                 2832769    5  0.10   0.50
001234          Los Angelos                    1234    1  0.10   0.10
0123456                                       23456    3  0.24   0.72
0123            Unknown                                4        -1.00
00134           Unknown                                5        -1.00
00123456789012  Unknown                                9        -1.00
0061234         Los Angelos                   61234  600  0.10  60.00
0061853279      Australia                    853279  300  1.40 420.00
00611234567890  Australia                1234567890  700  1.40 980.00
006112345678901 Unknown                              800        -1.00
123456789       Local                     123456789    2  0.00   0.00
123456789012345 Local               123456789012345    4  0.00   0.00

[rio]

Thanks, rickyliu!! Your io test helped me kill the bug and got AC.

[little joey]

rickyliu, your input is illegal on several places (numbers shouldn't be ambiguous, at least one digit after 00, etc.), and my AC solution prints something completely different.
Your last testcase helped me to find my bug, however, so thanks.

[rickyliu]

little joey, would you please specify which ones are ambiguous? I believe the input the judge used does not have STD calls with area code 0. So, your AC program outputs differently with mine.

[little joey]

Now I see what you mean. But no, I think that "00 Los Angelos" is not a legal code (STD codes should start with one zero, not two). But opinions may differ

[rickyliu]

I have the same understanding at the very beginning. I added that input case because someone in the forum said you had to consider this in order to get AC. The locality name should not contain spaces as well (as I can tell after finding the possible input the judge used) but someone also suggested to cater for this. Yes, there are many different opinions on the same problem

[UlMonkey1987]

I am experiencing WA when solving UVA-139, all cases available now have been tested, but WA still remains.

So I'm beginning to think about the possibility of tricks on this problem.

could anyone please tell me what kind of trick the UVA-Judge may be playing?


Thanks.