10009 - All Roads Lead Where?
Moderator: Board moderators
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.
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.
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;
}
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;
}
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]
[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]
-
- 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.
-
- 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.
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.
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.
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]
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]
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.
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...
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.