139 - Telephone Tangles

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ar2rd
New poster
Posts: 16
Joined: Sat Oct 22, 2005 2:05 am

139 WA - need input

Post by 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.
You're never too old to become younger...

Ruberik
New poster
Posts: 2
Joined: Mon May 26, 2003 4:16 am

139 contains lies

Post by 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
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

139 WA

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

139 PE

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

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

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

Post by Yu Fan »

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

rio wrote: 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by 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 :D

UlMonkey1987
New poster
Posts: 1
Joined: Sat Aug 07, 2010 11:04 am

139 Telephone Tangles

Post by 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.

Post Reply

Return to “Volume 1 (100-199)”