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

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Presentation Error 139

Post by paulhryu » Tue Apr 22, 2003 8:47 am

I am getting a Presentation Error for 139. I have tried many formatting devices, tabs, spaces, getting rid of trailing spaces, etc., and I keep getting Presentation Errors! I do not see any formatting information in the text, but some of the submissions have been accepted without Presentation Error, as I can see in the submissions page. Although technically Presentation Error is Accepted, I would still like to be able to have it be accepted with no error at all.

If you can tell me how to format the output, I would very much appreciate it. I think the problem description should have it.

Paul

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Still get WA 139

Post by Farid Ahmadov » Tue Nov 25, 2003 10:38 pm

Hello.
I am getting WA. Can anyone AC give me some tricky IO for this problem. I've tried all inputs on this forum. Is there something that I could miss?
_____________
NO sigNature

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Re: Problem 139 Why Invalid Memory Assignment

Post by chunyi81 » Sat May 08, 2004 5:23 pm

I am having the same problem. I am using 3 arrays, each of size 3000 to store the code,locality and the cost. Initially, I used a size of 1000, which gave RTE, then I increased to 2000, still RTE and now 3000, and still RTE. Here is my RTE code:

[c]
Resolved.
[/c]

My code can also handle input such as 015 Los Angeles$50, for example. The above code runs fine with the sample input. Is there any tricky input to this problem? Thanks for any help.
Last edited by chunyi81 on Mon May 10, 2004 4:19 am, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Problem 139 Why WA

Post by chunyi81 » Mon May 10, 2004 4:19 am

Nevermind. I found the problem with my code already.

Now I get WA. Is there any tricky input to this problem?

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Problem 139: Why WA

Post by chunyi81 » Mon May 10, 2004 9:40 am

I am also getting WA for this problem. I have tried the inputs in this forum and my program runs correctly on all of them. Is there any tricky input to this problem?

Here is my code:
[c]
AC
[/c]
Last edited by chunyi81 on Sat Jan 08, 2005 7:20 am, edited 3 times in total.

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Mon May 10, 2004 10:47 am

All the tricky input I know is that name should be read ( including space(s) ) until character '$'

hope it helps

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon May 10, 2004 12:13 pm

Almost Human wrote:All the tricky input I know is that name should be read ( including space(s) ) until character '$'

hope it helps
Thanks for your help. My code can handle those cases. I found a major bug already. My code is not handling the case such as:

0061 Australia$100
000000
006112345678 5
#

correctly. The correct output should have "Australia", but my program outputs "Unknown". Something is wrong with the conditions.

I changed the conditions to the correct one, but still WA.

Londovir
New poster
Posts: 4
Joined: Thu Dec 30, 2004 8:04 am

139 - Keep getting WA

Post by Londovir » Thu Dec 30, 2004 8:18 am

Okay, this problem is VERY frustrating to me! I've managed every angle I can think of to get past the WA on this one, and nothing is working.

I've gone and tried every test case from every post in this forum for #139 (Telephone Tangles), and come up with correct answers for each. I even went so far as to go and search the internet and found a site that had a 6 megabyte input file with a 6 megabyte output file from a programming contest (perhaps the original ACM one #139 came from), and ran it through my program. It came out exact to the byte with the contest correct answer. To my mind, I've got a correct program, but the online judge is still ruling it WA.

I check IDD and STD lengths for correctness, I check overall phone number length, I check for maximum code match (so that a code of 0125 doesn't overrule a code of 01253). I check all codes & numbers to ensure they are numeric only. I flag locals correctly, and unknowns correctly. I accept the entire location name (including any potential prefix spaces or suffix spaces).

I've coded everything from array storage to dynamic trees. I even wasn't entirely sure that chars were a "safe" storage format, so I tried encoding a wide character version of my program in case there were foreign characters (UNICODE) being used, and still got WA. I am at wits end.

There is apparently some input being used by the online judge which wasn't used in the programming contest, as I said that the 12000+ line input file from an archive site passed my program with flying colors. I've even seen people post that they had AC but it went to WA after this problem was rejudged.

Anyone with any pointers? I'm posting my code below. Thanks!

Londovir
-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct codenode LEAF;

struct codenode
{
char prefix[7];
char location[26];
long cost;
};


struct TREE
{
~TREE();

TREE *branch[10];
LEAF *leaf;
};

int isvalid(char *code)
{
char *tmpstr;

tmpstr = code;

while (*tmpstr != 0)
{
if (strcspn(tmpstr,"0123456789") != 0) return -1;
tmpstr++;
}

tmpstr = code;
if (*tmpstr != '0') return -1;
if (strlen(code) > 6) return -1;
if (strlen(code) < 2) return -1;

return 1;
}

void emptytree(TREE *intree)
{
for (int i=0; i < 10; i++) intree->branch = NULL;
intree->leaf = NULL;
}

void setlocaltree(TREE *intree)
{
for (int i=1; i < 10; i++)
{
intree->branch = new TREE;
emptytree(intree->branch);
intree->branch->leaf = new LEAF;
strcpy(intree->branch->leaf->prefix,"");
strcpy(intree->branch->leaf->location,"Local");
intree->branch->leaf->cost = 0;
}
return;
}

void treeadd(TREE *maintree, char *code, char *locale, long cost)
{
TREE *current = maintree;
char *tempcode = code;
int number;

// Verify the code's legit
if (isvalid(code) == -1) return;

while (*tempcode != 0)
{
number = *tempcode-'0';
if ((current->branch[number]) == NULL)
{
current->branch[number] = new TREE;
emptytree(current->branch[number]);
current = current->branch[number];
tempcode++;
}
else
{
current = current->branch[number];
tempcode++;
}
}

current->leaf = new LEAF;
strcpy(current->leaf->prefix,code);
strcpy(current->leaf->location,locale);
current->leaf->cost = cost;

return;
}

LEAF *rootout(TREE *maintree, char *code)
{
TREE *current = maintree;
char *tempcode = code;
int number;
int levels = 0;
char roots[7];
char *temproot = roots;

while (*tempcode != 0)
{
number = *tempcode-'0';
if (current->branch[number] == NULL)
{
// Can't match more, check to see if done
*temproot = 0;
if (tempcode != code)
{
// Verify valid number
if (levels == 1)
{
// Local
if ((strlen(code) < 4) || (strlen(code) > 10)) return NULL;
}
if (levels == 2)
{
// Definite STD
if ((strlen(code)-levels < 4) || (strlen(code)-levels > 7)) return NULL;
}
if (levels >= 3)
{
if (((roots[0] == '0') && (roots[1] == '0')) && ((strlen(code)-levels) < 4)) return NULL;
if (((roots[0] == '0') && (roots[1] == '0')) && ((strlen(code)-levels) > 10)) return NULL;
if (((roots[0] == '0') && (roots[1] != '0')) && ((strlen(code)-levels) < 4)) return NULL;
if (((roots[0] == '0') && (roots[1] != '0')) && ((strlen(code)-levels) > 7)) return NULL;
}
return current->leaf;
}
else
{
return NULL;
}
}
current = current->branch[number];
tempcode++;
levels++;
*(temproot++) = number+'0';
}

return NULL;
}

TREE::~TREE (void)
{
delete this->leaf;
for (int k=0; k < 10; k++) delete this->branch[k];

}

int main (void)
{
unsigned int index = 1;
char inln[2000];
char inlncopy[2000];
char acode[14];
char anarea[52];
long acost;
long minutes;

TREE *alltree;
LEAF *lentry;

alltree = new TREE;
emptytree(alltree);
setlocaltree(alltree);

while (gets(inln))
{
strcpy(inlncopy,inln);
strcpy(acode,strtok(inlncopy," "));

if (strcmp(acode,"000000") == 0) break;

strcpy(anarea,strtok(NULL,"$"));
acost = atoi(strtok(NULL,"\0"));

treeadd(alltree,acode,anarea,acost);
}

while (gets(inln))
{
sscanf(inln,"%s %ld\n",anarea,&minutes);
if (strcmp(anarea,"#") == 0) break;
lentry = rootout(alltree,anarea);
if (lentry)
{
sprintf(inln,"%-16s%-25s%10s%5ld%6.2lf%7.2lf",anarea,lentry->location,
(anarea+strlen(lentry->prefix)),minutes,(double)lentry->cost/100.0,
((double)lentry->cost*minutes/100.0));
puts(inln);
}
else
{
sprintf(inln,"%-16s%-25s%10s%5ld%6s%7.2lf",anarea,"Unknown",
"",minutes,"",-1.0);
puts(inln);
}
}

delete alltree;

return 0;

}

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sat Jan 08, 2005 7:14 am

Here is a statement from the problem description:

The second part contains the log and will consist of a series of lines, one for each call, containing the number dialled and the duration. The file will be terminated a line containing a single #. The numbers will not necessarily be tabulated, although there will be at least one space between them. Telephone numbers will not be ambiguous.

Your code does not handle this properly

input: (this is the sample input, modified)
088925 Broadwood$81
03 Arrowtown$38
0061 Australia$140
000000
031526 22
0061853279 3
0889256287213 122
779760
1
002832769 5
#

correct output:
031526 Arrowtown 1526 22 0.38 8.36
0061853279 Australia 853279 3 1.40 4.20
0889256287213 Broadwood 6287213 122 0.81 98.82
779760 Local 779760 1 0.00 0.00
002832769 Unknown 5 -1.00

your output:
031526 Arrowtown 1526 22 0.38 8.36
0061853279 Australia 853279 3 1.40 4.20
0889256287213 Broadwood 6287213 122 0.81 98.82
779760 Local 779760 122 0.00 0.00
1 Unknown 122 -1.00
002832769 Unknown 5 -1.00

Also, for local numbers, you are also not handling that properly in your code. I refer u to this statement in the problem description:
Local calls start with any digit other than 0 and are free.

It is not stated that for local calls the subscriber's number must have at least 4 digits. U are assuming that in your code.

input:
00 123$10
000000
1234 3
123 2
12 1
1 1

correct output:
1234 Local 1234 3 0.00 0.00
123 Local 123 2 0.00 0.00
12 Local 12 1 0.00 0.00
1 Local 1 1 0.00 0.00

your output:
1234 Local 1234 3 0.00 0.00
123 Unknown 2 -1.00
12 Unknown 1 -1.00
1 Unknown 1 -1.00

Londovir
New poster
Posts: 4
Joined: Thu Dec 30, 2004 8:04 am

That's an "interesting" problem statement...

Post by Londovir » Sat Jan 08, 2005 9:38 am

Okay, I'll grant that the Local Number support was broken in my code. Actually, that was not in my final code, but was something I hacked together to test an idea, and I simply posted the wrong version in this topic. My mistake on that one.

But, if the other issue you pointed out turns out to be what's keeping me from AC, I've got a major beef with the problem statement! As you quoted in your reply, it states quite clearly "The second part contains the log and will consist of a series of lines, one for each call, containing the number dialled and the duration." So, clearly, my program was producing the correct output (in that case, not counting the mixup with the local number cases) according to the stated problem description.

I, and I think many others who once had this AC but got WA after rejudging, obviously did not consider the possibility that a log entry could be broken over 2 lines. Perhaps not tabulated neatly into columns (or even with a specific number of white spaces between number and duration), but definitely expected to be on one line (terminated by a LF).

I'll "correct" my code tomorrow for this possibility and see if I get AC. Even so, the description should be changed....

Thanks for the pointers!!

Londovir

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

problem 139,145

Post by sunnycare » Mon Apr 18, 2005 5:10 am

i cant see the sample output clearly..

who can give me a clear explanation...
(the width of each part of the output)


thanks

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

about input output

Post by surya ss » Sat Jun 11, 2005 7:50 pm

for this input :
088925 Broad-wood$ 81
03 Arrow.town$ 38
0061 Australia$ 140
091244 teslocal$ 121
0911 N

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Jun 12, 2005 8:34 am

Hi surya ss,

Your sample input is not valid.

Read the problem description:
International (IDD) numbers start with two zeroes (00) followed by a country code (1-3 digits) followed by a subscriber's number (4-10 digits). National (STD) calls start with one zero (0) followed by an area code (1-5 digits) followed by the subscriber's number (4-7 digits). The price of a call is determined by its destination and its duration. Local calls start with any digit other than 0 and are free.

Read the input description:
Input will be in two parts. The first part will be a table of IDD and STD codes, localities and prices as follows:


Code Locality name$price in cents per minute
where represents a space. Locality names are 25 characters or less.

The log entries could be broken over two lines.

I will give you a test case:

Input:
088925 Broad-wood$ 81
03 Arrow.town$ 38
0061 Australia$ 140
091244 teslocal$ 121
0911 N

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

still WA

Post by surya ss » Mon Jun 13, 2005 8:03 am

hi chunyi81,
I have try all input in this board, but I still got WA,
here is my test input :

088925 Broad-wood$ 81
0001 aa $1
01 bb $ 3
03 Arrow.town$ 38
0061 Australia$ 140
091244 teslocal$ 121
0911 N

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

139-PE-Can anybody with ACC code give me 1 output?

Post by Cytoplasm » Wed Aug 03, 2005 5:51 pm

because I've tried a lot of things and its still PE. I hate those response graphs instead of real responses!

Post Reply

Return to “Volume 1 (100-199)”