## 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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Razib, I tried to copy-paste your code and ran the sample input. Funny that I just got blank-lines as output ...

I used gcc ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:
thanx man for ur help...
actually my word size was too small...so I was getting WA..

I fixed it & got AC..

thanx again for ur assistance
Wisdom is know what to do next; virtue is doing it.

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:

### 10009

Ok.
The problem clearly states this:
A city will never be paired with itself in a query.
So I wrote a little program to see if the judge abides by this rule:

[cpp]
#include <iostream>
#include <string>

using namespace std;

bool connect[50][50];

int main()
{
int M,N;
cin >> M >> N;

string s1,s2;
int c1,c2;
for (int i=0; i < M; i++)
{
cin >> s1 >> s2;
c1=s1[0]-'A'; c2=s2[0]-'A';
connect[c1][c2]=connect[c2][c1]=true;
}

for (int i=0; i < N; i++)
{
cin >> s1 >> s2;
c1=s1[0]-'A'; c2=s2[0]-'A';
if (c1 == c2) int x=1/0;
}

return 0;
}
[/cpp]

And well, guess what!
I get a run time error.
meaning c1 == c2 when it obviously shouldn't.

Note to judges: If you can't insure the input is correct atleast provide it for us, as my time is more precious than wasted on crap like this.
-------------------------------------------
"my name is amir"
-amir

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:

### no one seems to reply

well, no one seems to want to reply to my message so i'll get to a more practical issue at hand:

how am i supposed to handle the case where c1 == c2 ? what am i to output.

I'm also curious as to why this program may have different answers, i.e. why is the checkmark blue? i did a little sketching and there can only be one shortest path in tree. could someone please provide me with a counter example. or reply.
-------------------------------------------
"my name is amir"
-amir

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
this problem is a multiple input problem...that's why it's marked with blue tick...
http://acm.uva.es/problemset/minput.html
check it and tell us if you got further problem...
Greetings
Istiaque Ahmed [the LA-Z-BOy]

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Contact:

### thanks a lot

Thanks a lot. I had yellow and blue confused. I got AC
-------------------------------------------
"my name is amir"
-amir

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

### 10009 - All roads lead where?

Hi ppl, I'm going mad with this problem...
Could anyone please tell me what's wrong?

[c]I erased my code because it's only mistake was that I didn't reset the array to handle multiple input...[/c]

wonderboy
New poster
Posts: 4
Joined: Thu Oct 17, 2002 10:21 pm
Location: India
Contact:

### 10009 Helllppp!!!!

Hello everyone,
I don't know why I keep getting a "Runtime Time Error" for this problem. OJ says there's an invalid memory reference. My program handles multiple input and if you see the code, you will notice that I have declared bigger arrays than required (actually needed of size 27) just to stay on the safe side. I have used Floyd-Warshall's algo. Please can anyone check my program with some input and help me in finding the bug. I have seen it a hundred times and can't figure it out . Thanks in advance for all the help.

Cheers!!!

Code: Select all

``````Deleted after getting AC. Didn't handle multiple input properly and also underestimated the city names length.
``````
Last edited by wonderboy on Fri Oct 03, 2003 10:11 pm, edited 1 time in total.

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Contact:
This problem has a astonishing idea. It has very very large city name. I can not figure out but of course more than 40000 chars. I got ac after resizing my array with 100000. U can try it. But the idea of the problemsetter is just annoying I think.
From 0 to 0

wonderboy
New poster
Posts: 4
Joined: Thu Oct 17, 2002 10:21 pm
Location: India
Contact:
Thanx Towhid for the help. Phew!! Finally got the AC. Actually, I had done two mistakes : First, my program didn't handle multiple inputs properly. I hadn't read the minput.html page properly. Then the mistake you had pointed out. I also had to use arrays of 100000 characters. I completely agree with you that this kind of input is very annoying. There's no point in testing the programming skills with such things. Anyway, I am relieved now.

jambon_vn
New poster
Posts: 15
Joined: Wed Sep 29, 2004 6:03 am

### 10009 - WA :((

Can anyone point out my mistake? Thank.

Code: Select all

``````#include <iostream>
#include <string>

using namespace std;

long Num, M, N, numB, numC;
int A[27], B[27], C[27];

int main()
{
cin >> Num;
for (long k = 1; k <= Num; k++)
{
cin >> M >> N;

long i;

for (i = 1; i <= M; i++)
{
string city1, city2;
cin >> city1 >> city2;
A[city2[0] - 'A'] = city1[0] - 'A';
}

for (i = 1; i <= N; i++)
{
string city1, city2;
cin >> city1 >> city2;
long S = city1[0] - 'A';
long F = city2[0] - 'A';

long des = 'R' - 'A';

numB = 0;
while (S != des)
{
B[++numB] = S;
S = A[S];
}

numC = 0;
while (F != des)
{
C[++numC] = F;
F = A[F];
}

while (B[numB] == C[numC])
{
des = B[numB];
numB--;
numC--;
}

long j;
for (j = 1; j <= numB; j++) cout << (char) (B[j] + 'A');
cout << (char) (des + 'A');
for (j = numC; j >= 1; j--) cout << (char) (C[j] + 'A');
cout << endl;
}

if (k < Num) cout << endl;
}
return 0;
}
``````

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China

### 10009

I know the city name is very long. So I just read the first letter of each name and skip the other letters. But still the Runtime Error (SIGSEGV)

Code: Select all

``````int case,m,n;
char city1,city2,c;
scanf("%d",&case);
while(case-->0){
scanf("%d %d",&m,&n);
c=getchar();/*eat the '\n'*/
while(m-->0){
city1=getchar();
while(c!=' ')/*skip letters until the space*/
c=getchar();
city2=getchar();
while(c!='\n')/*skip letters until the '\n'*/
c=getchar();}
while(n-->0){
...../*the same as the process of the loop of m*/}}``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
My AC program assumes city's name is at most 1024 characters, so there's no need to read input by character.

Yile
New poster
Posts: 17
Joined: Sun Feb 27, 2005 10:36 am
Location: China
Thanks, I've found the bug of my program and got AC. The length of the name doesn't cause the bug as you expect. Thank you again.

Fali
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

### 10009 - I need some help

Here is my code, i