OJ Board

Posted: **Sun Jan 28, 2007 12:10 pm**

I have read many threads about this problem.But I still can't get Accepted.
Who can help me?Please give me some cases I can't handle or point out my mistake.Thanks very much.

The following is my code:

Code: Select all

Accepted!

Posted: **Mon Jan 29, 2007 12:23 pm**

Try this:

Code: Select all

A:DBC. A B 20
#

Your answer is:

Code: Select all

/C

The correct answer should be:

Code: Select all

/D

Posted: **Tue Jan 30, 2007 8:13 am**

Thank you very much!
Your test case is very helpful to me.
I changed my code a little and get AC!
then I will delete my code above.
Thanks again.

Posted: **Sun Jun 19, 2011 11:32 pm**

Try This
Input

Code: Select all

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 1
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 6
A:BCD;B:ACD;C:ABD;D:ABCG;G:DEFH;E:GFH;F:GEH;H:EFG. A C 7
A:B;B:A. B A 3
A:B;B:C;C:A. B A 6
C:A;A:B. A C 999999999
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 1
A:DBC. A B 20
A:DBC. A B 1
A:BC:A A B 1
#

Output:

Code: Select all

D F G /E
A B C D G E F /H
C D /B
A B D /C
/B
A /C
/B
D F G /E
A B D G E F /H
/D
A /D
/A

Posted: **Mon Apr 16, 2012 4:28 pm**

rickyliu wrote:Try this:
Code: Select all
A:DBC. A B 20
#
Your answer is:
Code: Select all
/C
The correct answer should be:
Code: Select all
/D

Hello, please explains why the answer is /D? If I understand the problem correctly, the graph should be like this:

And

where in this case the Minotaur checks the exits from a cavern in alphabetical order

So Minotaur should go to C (because C < D) and be trapped there immediately?

Posted: **Mon Apr 16, 2012 11:21 pm**

Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input

Code: Select all

A:DBC. A B 20
#

The Minotaur will attempt to go from A first to D, then B, then C.

Posted: **Tue Apr 17, 2012 2:51 pm**

brianfry713 wrote:Read the problem description again. It was alphabetical just for the sample case. "The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them"

In the input
Code: Select all
A:DBC. A B 20
#
The Minotaur will attempt to go from A first to D, then B, then C.

Thank you, I got it!

Posted: **Tue Apr 17, 2012 9:13 pm**

I wonder which test case that cause the TLE. Here is my code, please give me some big case and I will try to improve it.

(My program return results correctly for problems at this topic: http://online-judge.uva.es/board/viewto ... =1&t=14236)

Code: Select all

import java.util.ArrayList;
import java.util.Scanner;


public class Main {

	//===============================================//
	// Inner Classes
	//===============================================//
	
	public class ArrayListInteger {
		public ArrayList<Integer> value = new ArrayList<Integer>();
	}
	
	//===============================================//
	// Variables
	//===============================================//
	
	private static ArrayListInteger[] mAdjacentVertexes;
	private static boolean[] mVertexDisabled;
	private static int mFinalVertex = 0;
	private static int mThesusVertex = 0;
	private static int mMinotaurVertex = 0;
	private static int mK = 0;
	
	//===============================================//
	// Public Methods
	//===============================================//
	
	public static void parseInput(String pRawData) {
		String[] periodDelimiter = pRawData.split("\\.");
		
		String[] passages = periodDelimiter[0].split(";");
		for (int i = 0; i < passages.length; i++) {
			int startVertex = passages[i].charAt(0) - 'A';
			if (startVertex > mFinalVertex) mFinalVertex = startVertex;
			
			for (int j = 2; j < passages[i].length(); j++) {
				int endVertex = passages[i].charAt(j) - 'A';
				if (endVertex > mFinalVertex) mFinalVertex = endVertex;
				
				mAdjacentVertexes[startVertex].value.add(endVertex);
			}
		}
		mFinalVertex++;
		
		String initData[] = periodDelimiter[1].trim().split(" ");
		mMinotaurVertex = initData[0].charAt(0) - 'A';
		mThesusVertex = initData[1].charAt(0) - 'A';
		mK = Integer.parseInt(initData[2]);
	}

	public static String traverse() {
		String result = "";
		
		int mTravelCount = 0;
		int nextVertex = -1;
		do {
			nextVertex = -1;
			
			for (int i = 0; i < mAdjacentVertexes[mMinotaurVertex].value.size(); i++) {
				int currentVertex = mAdjacentVertexes[mMinotaurVertex].value.get(i);
				if (mVertexDisabled[currentVertex] || currentVertex == mThesusVertex) continue;
				nextVertex = currentVertex;
				break;
			}
			
			if (nextVertex != -1) {
				mTravelCount++;
				if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)
					mThesusVertex = mMinotaurVertex;
				mMinotaurVertex = nextVertex;
				
				if (mTravelCount == mK) {
					// Print result
					result += (char)(mThesusVertex + 'A') + " ";
					
					// Clear this vertex
					mVertexDisabled[mThesusVertex] = true;
					
					mTravelCount = 0;
				}
			}
		} while (nextVertex != -1);
		result += "/" + (char)(mMinotaurVertex + 'A');
		
		return result;
	}
	
	public static void main(String[] args) {
		String result = "";
		Scanner scanner = new Scanner(System.in);
		
		// Initialize
		mAdjacentVertexes = new ArrayListInteger[26];
		Main obj = new Main();
		for (int i = 0; i < 26; i++) {
			mAdjacentVertexes[i] = obj.new ArrayListInteger();
		}
		mVertexDisabled = new boolean[26];
		
		String currentInput = scanner.nextLine();
		while (!currentInput.equals("#")) {
			
			// Reset value
			for (int i = 0; i < 26; i++) {
				mAdjacentVertexes[i].value.clear();
				mVertexDisabled[i] = false;
			}
			mFinalVertex = 0;
			
			// Input
			parseInput(currentInput);
			
			// Traverse
			result += traverse() + "\n";
			
			// Next line
			currentInput = scanner.nextLine();
		}
		
		System.out.print(result);
	}
	
}

Thank you.

Posted: **Tue Apr 17, 2012 10:58 pm**

Input:

Code: Select all

B:A;A:B. A C 999999999
#

AC output:

Code: Select all

/B

Posted: **Wed Apr 18, 2012 7:52 am**

Thank you brianfry713,

Maybe I'm having too much misunderstanding about this problem. In that test case,

If a cavern has no exit it may or may not be in the input.

So C doesn't have any connection with A and B, so Theseus cannot chase the Minotaur? Then if I try comment out this line:

Code: Select all

if (mAdjacentVertexes[mThesusVertex].value.indexOf(mMinotaurVertex) != -1)

So Theseus can freely chase after Minotaur, the program works well with that test case, but I still get another TLE.

Posted: **Thu Apr 19, 2012 1:05 am**

Yeah that test case I posted is probably invalid but the line you commented out is not needed to get AC and will slow down your code.
I optimized your code and got AC in 1.392 sec. JAVA is always going to be slow, so make sure you are coding efficiently and sometimes you should try C/C++ instead. Use BufferedReader and BufferedWriter for I/O. mFinalVertex is not needed so get rid of it. Building the entire output into a string is slower than printing it immediately onto a BufferedWriter.

Posted: **Thu Aug 02, 2012 8:42 am**

For every case above, my code gives correct output. But why I am getting wrong answer????

Please someone help me. Thanks in advance. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}

Posted: **Mon Aug 13, 2012 12:26 pm**

Oh God, Please someone help me, Please someone tell me what will be the output of the following cases...

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3

Please someone help me.

Posted: **Mon Aug 13, 2012 12:56 pm**

Please help me to find why I am getting wrong answer in this problem. Here is my code....

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
char st[250];
long i,n,ts,mt,k,vis[35],c,sz;
vector<long>vc[35],op;
bool fg;
int main()
{
	while(gets(st) && strcmp(st,"#"))
	{
		for(i=0;i<30;i++)
		{
			vc[i].clear();
			vis[i]=0;
		}
		for(i=0;st[i];i++)
		{
			if(st[i]>='A' && st[i]<='Z')
			{
				n=st[i]-65;
				i+=2;
				while(st[i]>='A' && st[i]<='Z')
				{
					vc[n].push_back(st[i]-65);
					i++;
				}
			}
			if(st[i]=='.')
			{
				mt=st[i+2]-65;
				ts=st[i+4]-65;
				k=st[i+6]-'0';
				break;
			}
		}
		c=0;
		while(1)
		{
			fg=0;
			sz=vc[mt].size();
			for(i=0;i<sz;i++)
			{
				n=vc[mt][i];
				if(vis[n] || n==ts)
					continue;
				else
				{
					c++;
					fg=1;
					ts=mt;
					mt=n;
					if(c==k)
					{
						op.push_back(ts);
						vis[ts]=1;
						c=0;
					}
					break;
				}
			}
			if(fg==0)
				break;
		}
		sz=op.size();
		for(i=0;i<sz;i++)
			printf("%c ",op[i]+65);
		printf("%c%c\n",47,mt+65);
		op.clear();
	}
	return 0;
}

Please help me.. What will be the output for these case.....

Code: Select all

A:BCD;B:AD;C:AD;D:B. A C 3
A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG. A C 3

Thanks in advance....

Posted: **Mon Aug 13, 2012 11:23 pm**

http://www.uvatoolkit.com/problemssolve.php

OJ Board

168 - Theseus and the Minotaur

168 Now ACed,ignore it

Re: 168 Now ACed,ignore it

Re:

Re: 168 Now ACed,ignore it

Re: 168 Now ACed,ignore it

168 - Theseus and the Minotaur TLE

Re: 168 - Theseus and the Minotaur TLE

Re: 168 - Theseus and the Minotaur TLE

Re: 168 - Theseus and the Minotaur TLE

Re: 168 Now ACed,ignore it

Re: 168 Now ACed,ignore it

Re: 168 - Theseus and the Minotaur TLE

Re: 168 - Theseus and the Minotaur TLE