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

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Mon Sep 05, 2005 2:56 pm

I took your source code and compiled in my computer. First, i tested with the following case.

Code: Select all

1

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa
Your program prints a blank line as the output.

I tried some more.

Code: Select all

4

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa

8 3
Rome Chittagong
Rome Khulna
Rome Pabna
Rome Sylhet
Sylhet Moulovibazar
Chittagong Bandorban
Pabna Gaibandha
Rome Barisal
Rome Chittagong
Khulna Gaibandha
Pabna Sylhet

6 1
Rome BUET
BUET TSC
TSC Shahbag
Sahbag Nilkhet
Nilkhet Katabon
Katabon ElephantRoad
ElepehantRoad Rome
The correct output should be:

Code: Select all

TRP
MTRPF
AVTG

TRP
MTRPF
AVTG

RBC
KRPG
PRS

EKNSTBR
Your Program says:

Code: Select all

TG

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Thu Oct 27, 2005 3:33 pm

I 've declared array big enough to read lines from input file, still i am getting runtime error (after executing for around 00.00.039s), i am trying FLOYD-WARSHALL to solve this... would anyone care to tell me why else i may get RE ???

[to Yile, what was your fault in your code??? may be same here :-?]
[EDIT: code is now attached, please,feel free to run this code and check if it fails (it sure does :-?) ... HELP]

Code: Select all

/*
	10009
	All Roads Leas Where?
*/

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


void print_path(int i, int j);

long parent[26][26], d[26][26];

char str[1000000], *p;
int main()
{
	int m, n, i, j, k, u, v, test;

	long temp;


	gets(str);
	p = strtok(str, " ");
	test = atoi(p);

	gets(str);

	while (test --)
	{
		gets(str);

		p = strtok(str, " ");
		m = atoi(p);

		p = strtok(NULL, " ");
		n = atoi(p);


		for (i=0; i<26; i++)
		{
			for (j=0; j<26; j++)
			{
				if (i == j)
					d[i][j] = 0;
				else
					d[i][j] = INT_MAX - 200;
			}
		}

		for (i=0; i<m; i++)
		{
			gets(str);

			p = strtok(str, " ");
			u = (int)(p[0] - 'A');

			p = strtok(NULL, " ");
			v = (int)(p[0] - 'A');

			d[u][v] = d[v][u] = 1;

		}

		for (i=0; i<26; i++)
			d[i][i] = 0;

		for (i=0; i<26; i++)
		{
			for (j=0; j<26; j++)
			{
				if ((i == j) || (d[i][j] == INT_MAX - 200))
				{
					parent[i][j] = -1;
				}

				else if ((i != j) && (d[i][j] < INT_MAX - 200))
				{
					parent[i][j] = i;
				}
			}
		}

		for (k=0; k<26; k++)
		{
			for (i=0; i<26; i++)
			{
				for (j=0; j<26; j++)
				{
					temp = (d[i][k] + d[k][j]);

					if (temp < d[i][j])
					{
						d[i][j] = temp;
						parent[i][j] = parent[k][j];
					}


				}


			}
		}

		for (i=0; i<n; i++)
		{
			gets(str);


			p = strtok(str, " ");
			u = (int)(p[0] - 'A');

			p = strtok(NULL, " ");
			v = (int)(p[0] - 'A');

			print_path(u, v);
			printf("\n");
		}

		if (gets(str) == NULL)
			break;
		else
			printf("\n");
	}




	return 0;
}


void print_path(int i, int j)
{
	if (i == j)
		printf("%c", 'A' + i);

	else
	{
		print_path(i, parent[i][j]);
		printf("%c", 'A' + j);
	}
}



QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao » Tue Mar 14, 2006 9:30 pm

you 3 test is WRONG:
Rome Chittagong
...
Chittagong Bandorban
Rome Barisal
HERE Bandorban Barisal with same 1 letter It can't be!

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Thu Mar 16, 2006 4:41 pm

I know its wrong, i did not put a wrong test case here for nothing.

I did not check for name of more than one place starting with the same letter. But i got ACC. this implies there is no such case in the judge data. We have to produce only the correct output, remembe ? does not matter how you generate it.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

10009 All roads lead where Wrong Ans

Post by ayeshapakhi » Thu Jul 20, 2006 2:38 pm

I dont understand why it is WA.
pls help me. and send some i/o if possible.
thanks .

Code: Select all

removed after getting AC;
Last edited by ayeshapakhi on Sun Jul 23, 2006 8:06 am, edited 1 time in total.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10009 All roads lead where Wrong Ans

Post by tan_Yui » Thu Jul 20, 2006 7:29 pm

Try this input. :)


Input :
2

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa

25 5
Rome Apple
Rome Kiwi
Rome Salt
Apple Bruteforce
Apple Circumstance
Apple Delete
Kiwi Linear
Kiwi Multiple
Salt Telescope
Salt Ultimate
Bruteforce Egg
Bruteforce Fire
Circumstance Ghost
Circumstance Honest
Delete Iterate
Delete Joker
Linear Null
Linear Optimize
Multiple Pointer
Multiple Queue
Telescope Venus
Ultimate Wheel
Ultimate Xylitol
Ultimate Yellow
Yellow Zero
Egg Zero
Zero Egg
Salt Queue
Rome Venus
Ultimate Circumstance
Output :
TRP
MTRPF
AVTG

EBARSUYZ
ZYUSRABE
SRKMQ
RSTV
USRAC
But, your code outputs :
TRP
MTRPF
AVTG

EBARSUYZ
ZYUSRABE
STMQ
RAV
USRAC
When your code tries only second case input, the output is same as correct one. But in above case, your code failed.
Although I don't read your code well, I think the cause of WA is initialization of array 'mat'.

Best regards.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Sun Jul 23, 2006 8:11 am

Dear tan_Yui,
thanks a lot for ur nice advice.
i forgot to initialize the adjacency matrix, :(
it is ok now.
Thanks again;
....... :D

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

10009 - All Roads Lead Where? ----- WA

Post by kangroo » Sat Oct 11, 2008 9:49 am

hi everybody,

now got AC... :D :D
there should not be any blank line after the last test case...
Last edited by kangroo on Sat Oct 11, 2008 9:58 am, edited 1 time in total.

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

10009 - All Roads Lead Where?

Post by kangroo » Sat Oct 11, 2008 9:53 am

I ve a doubt in the 3rd test case provided by Raiyan Kamal

8 3
Rome Chittagong
Rome Khulna
Rome Pabna
Rome Sylhet
Sylhet Moulovibazar
Chittagong Bandorban
Pabna Gaibandha
Rome Barisal
Rome Chittagong
Khulna Gaibandha
Pabna Sylhet


his output were :
RBC
KRPG
PRS

------------------------------------
but for the first query , Rome ----> Chittagong , "RC" is the correct answer as there is a direct path between these two cities...so "RBC" is wrong...

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 10009 - All Roads Lead Where?

Post by receme » Fri Jun 10, 2011 1:20 pm

I have got RE.... Please help.


Here is my code.

Code: Select all

Got accepted. Silly mistake....

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 10009 - All Roads Lead Where?

Post by pranon » Mon Jul 23, 2012 3:05 pm

My code is being judged ``Wrong Answer" for some reason. Can anyone provide some i/o where my code fails?

Code: Select all

AC :D should always remember to remove or comment my debugging mess. :D
Thanks in advance! And sorry about the mess I've made of it in attempts at debugging! :(
Pranon
Last edited by pranon on Tue Jul 24, 2012 9:25 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10009 - All Roads Lead Where?

Post by brianfry713 » Mon Jul 23, 2012 10:54 pm

There are not any numbers in the sample output.
Last edited by brianfry713 on Sat Dec 29, 2012 9:31 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 10009 - All Roads Lead Where?

Post by pranon » Mon Jul 23, 2012 11:38 pm

I'm extremely sorry for not noticing this.
This has become a habit of mine, doing a lot of changes to the code, and forgetting to remove the debug statements. I recently did this in a contest as well, :'(
However Thanks a LOT! :D

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 10009 - All Roads Lead Where?

Post by @ce » Fri Dec 28, 2012 7:09 pm

Getting RE...plzz help

Code: Select all

AC
Last edited by @ce on Wed Jan 02, 2013 7:41 am, edited 1 time in total.
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10009 - All Roads Lead Where?

Post by brianfry713 » Sat Dec 29, 2012 10:27 pm

main should return 0
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”