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:

Post by turuthok » Wed Apr 09, 2003 9:53 pm

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
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Mon Apr 14, 2003 9:15 am

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
Location: Canada
Contact:

10009

Post by amir2099 » Wed Jun 18, 2003 3:51 pm

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
Location: Canada
Contact:

no one seems to reply

Post by amir2099 » Fri Jun 20, 2003 4:14 am

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

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Fri Jun 20, 2003 7:50 am

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
Location: Canada
Contact:

thanks a lot

Post by amir2099 » Sat Jun 21, 2003 3:34 pm

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?

Post by playerX » Tue Aug 26, 2003 4:00 pm

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]

Thanks in advance.

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

10009 Helllppp!!!!

Post by wonderboy » Mon Sep 29, 2003 8:11 pm

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 :x. 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
Location: Bangladesh
Contact:

Post by Towhid » Fri Oct 03, 2003 2:41 pm

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:

Post by wonderboy » Fri Oct 03, 2003 10:19 pm

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 :((

Post by jambon_vn » Wed Sep 29, 2004 6:18 am

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;
}

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

10009

Post by Yile » Mon Mar 14, 2005 4:26 pm

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:

Post by mf » Mon Mar 14, 2005 5:10 pm

My AC program assumes city's name is at most 1024 characters, so there's no need to read input by character.

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

Post by Yile » Tue Mar 15, 2005 8:44 am

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

Post by Fali » Thu Aug 18, 2005 8:04 pm

Here is my code, i

Post Reply

Return to “Volume 100 (10000-10099)”