## 10009 - All Roads Lead Where?

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

Moderator: Board moderators

Grzesiek
New poster
Posts: 8
Joined: Thu Feb 14, 2002 2:00 am

### 10009 - All Roads Lead Where?

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.
Regards, Grzesiek.

MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am
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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
You are aware multiple input, right ?

MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am
Oh!.. You are right, thanks..

splutter
New poster
Posts: 2
Joined: Tue Apr 23, 2002 7:22 am
multiply input?
did u mean that something is missing in the problem description?

splutter
New poster
Posts: 2
Joined: Tue Apr 23, 2002 7:22 am
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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

### 1000-character-long city names???!?

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
New poster
Posts: 2
Joined: Sat Nov 16, 2002 6:07 am
I don' t think there is loop which didn' t indicate in the question.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### multiinput

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
New poster
Posts: 8
Joined: Thu Feb 14, 2002 2:00 am

### 10009 - is this really "multiple input"?

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
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden
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
New poster
Posts: 8
Joined: Thu Feb 14, 2002 2:00 am
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
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

### 10009: why WA?

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.
``````
Last edited by razibcse on Mon Apr 14, 2003 9:23 am, edited 1 time in total.
Wisdom is know what to do next; virtue is doing it.

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:
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?
Wisdom is know what to do next; virtue is doing it.