10009 - All Roads Lead Where?

[Grzesiek]

Hi, I see loops in the input data.
The program does the following:
1) For all 26 towns: Town.prevTown = -1;
2) Next, according to input data:
...
Atown Btown
...
it is done: Town.prevTown = A.
(this is done only with the first part of
data, not with queries).
3) The following procedure is called:

void test_for_dead_loops(){
int i,j,n;
for( i=0; i<26; i++ ){
n = 0;
for( j=i; j>=0; j=Town[j].prevTown )
if( ++n > 30 ){
printf("dead loopn");
GenerateCrash();
}
}
}

GenerateCrash(), which is division by zero,
is reached. I see it as Runtime Error.

What to do? Should I assume that loops are
possible?
On the testing data the program runs
correctly.

[MegaS]

I can't find a error in my program - I even
see that there can be no bugs. Please help to find a bug in:
#include <stdio.h>

const int u=27;
const long max=100000;

//#define _BUG_

long n,p,i,j,k,r;
long a,w;
char ch;

FILE *f,*f1;

long readCity(){
fscanf(f," ");
fscanf(f,"%c",&ch);
r=ch-'A';
fscanf(f,"%*[a-zA-Z]s");
return r;
}

void print(long a, long b) {
if (w[a]==max) return;
print(a,w[a]);
fprintf(f1,"%c",char('A'+w[a]));
print(w[a],b);
return;
}

int main() {
#ifdef _BUG_
f=fopen("input.txt","r");
f1=fopen("output.txt","w");
#else
f=stdin;
f1=stdout;
#endif
for (i=0; i<u; i++)
for (j=0; j<u; j++) {
a[j]=max;
w[j]=max;
}
fscanf(f,"%ld%ld",&n,&p);
for (i=0; i<n; i++) {
j=readCity();
k=readCity();
a[j][k]=1;
a[k][j]=1;
w[j][k]=max;
w[k][j]=max;
}
for (k=0; k<u; k++)
for (i=0; i<u; i++)
for (j=0; j<u; j++)
if (a[j]>a[k]+a[k][j]) {
a[j]=a[k]+a[k][j];
w[j]=k;
a[j]=a[k]+a[k][j];
w[j]=k;
}
for (i=0; i<p; i++) {
j=readCity();
k=readCity();
fprintf(f1,"%c",char('A'+j));
print(j,k);
fprintf(f1,"%cn",char('A'+k));
}
#ifdef _BUG_
fclose(f1);
#endif
return 0;
}

[arnsfelt]

You are aware multiple input, right ?

[MegaS]

Oh!.. You are right, thanks..

[splutter]

multiply input?
did u mean that something is missing in the problem description?

[splutter]

still WA, can someone help me with my code~ thx
[cpp]#include "iostream.h"

int m,n,a[26][26],b[26][26];

void out(int x, int y)
{
if (b[x][y]!=-1) {
out(x,b[x][y]);
out(b[x][y],y);
} else {
cout << char(x+65);
}
}

int main()
{
char city1[1000], city2[1000];
int i,j,k;
while (cin >> m >> n) {
for (i=0; i<26; i++) {
for (j=0; j<26; j++) {
a[j]=-1;
b[j]=-1;
}
}
for (k=0; k<m; k++) {
cin >> city1 >> city2;
a[city1[0]-'A'][city2[0]-'A']=1;
a[city2[0]-'A'][city1[0]-'A']=1;
}

for (k=0; k<26; k++) {
for (i=0; i<26; i++) {
if (a[k]>0) {
for (j=0; j<26; j++) {
if (a[k][j]>0) {
if (a[j]<0 || a[j]>a[k]+a[k][j]) {
a[j]=a[k]+a[k][j];
b[j]=k;
}
}
}
}
}
}

for (k=0; k<n; k++) {
cin >> city1 >> city2;
if (city1[0]!=city2[0]) {
out(city1[0]-'A',city2[0]-'A');
}
cout << city2[0] << endl;
}
cout << endl;
}
return 0;
}
[/cpp]

[Adrian Kuegel]

Multiple input means, that there is first a number of test cases in the input file, but there is a exact description at http://acm.uva.es/problemset/minput.html But this is not mentioned in the problem description, you see it by the color of the icon before the problem name.

[SnapDragon]

splutter, I was having huge problems with this one, but I (after many experimental submissions) finally figured out why UVA's test set was killing my program. Like you, I had a 1000-char array to store the city names. Simply changing that from 1000 to 100,000 changed my result from a "Runtime Error" to "Accepted". In other words, they're giving city names that are longer than 1,000 characters! Talk about inane.

[zyc]

I don' t think there is loop which didn' t indicate in the question.

[stcheung]

I don't think there can be any loop at all for this problem.
Did you already know that this problem is multi input? I didn't realize that and I kept getting Time Limit Exceeded. You can go to the problems index to look for a description of multi input.

[Grzesiek]

With use of the following program I tested correctness of
input data format. I get Runtime Error (result of call to
GenerateCrash). Can anybody tell me what is wrong?

Grzesiek

#include <stdlib.h>
#include <stdio.h>

int aInt=123, Zero=0;

void GenerateCrash(){
aInt /= Zero;
exit(1);
}

char buf[300];

int main(){
FILE *f = stdin;
int nmi,imi;
fgets(buf,sizeof(buf),f);
if( sscanf(buf,"%d",&nmi) != 1 ) GenerateCrash();
for( imi=0; imi<nmi; imi++ ){
fgets(buf,sizeof(buf),f); /*skip the blank line*/
int M,N;
fgets(buf,sizeof(buf),f);
if( sscanf(buf,"%d%d",&M,&N) != 2 ) GenerateCrash();
for( int i=0; i<(M+N); i++ ){
fgets(buf,sizeof(buf),f);
}
}
return 0;
}

[cpp][/cpp]

[Astrakan]

You could try to make a solution that doesn't care about missing blank lines between cases. My solution ignores blank lines, so I don't know if the input has blank lines or not. You could also try to make the buffer bigger, if there are really long lines, since the maximum length of a city name is not specified.

[Grzesiek]

Thanks Astracan, that was it. Names are probably longer than
30000 (this is what i tried and what failed).
It looks that 10009 is more oriented to data reading technics
rather then to what it looks for the firs glance.

[razibcse]

This program is always getting WA...

I can't understand where the problem is...
I checked for multiple input..it didn't work...
Does the position of Rome make sense to other cities? I think
by default, Rome is the starting point, and input will be given
as such...
I made the list of cities first & then made the position of Rome 0.
Is this correct?

pls someone suggest me what to do & give some special input if any...

Code: Select all

The code has been deleted, after it got AC.

[razibcse]

someone pls see the code and tell me what to do to prevent WA..

i din't find any mistake..

is there some special input?