OJ Board

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

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?

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.

Nevermind. I found the problem with my code already.

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

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]

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

hope it helps

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.

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;

}

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

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

i cant see the sample output clearly..

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


thanks

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

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

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

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