10047 - The Monocycle

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

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

10047 - The Monocycle

Post by Farid Ahmadov » Tue Nov 04, 2003 7:33 pm

I am getting WA. Here some tests that I tried my progam on. Are these answers correct?

INPUT

Code: Select all

1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
5 5
#S#..
#.#..
#.###
#...T
#####
10 10
S.........
..........
..........
..........
..........
..........
..........
..........
..........
........T.
3 3
ST#
##.
.#.
25 25
S........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
........................T
6 6
#.#...
#.S.#.
#####.
#..#..
#T##..
......
0 0
OUTPUT

Code: Select all

Case #1
destination not reachable

Case #2
minimum time = 49 sec

Case #3
minimum time = 17 sec

Case #4
minimum time = 30 sec

Case #5
minimum time = 14 sec

Case #6
minimum time = 55 sec

Case #7
minimum time = 30 sec
If these tests are correct please give me some other ones.
Thank you.
_____________
NO sigNature

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Thu Nov 06, 2003 7:23 pm

Hey People. Help. Won't anybody help me? :cry:
_____________
NO sigNature

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Thu Nov 06, 2003 7:35 pm

my ac program gives the same output

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Nov 07, 2003 4:08 pm

Any I/O please.
_____________
NO sigNature

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Sat Mar 20, 2004 8:45 am

i keeps WA too.... it's terrible my code has 1000 ~lines


Can u give more tests....




:lol:

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Wed Mar 31, 2004 2:57 pm

Yeah....

i got AC.

thanks to everyone....



it is not hard task.... ;-)


Regards
MIras

Renato
New poster
Posts: 5
Joined: Wed Oct 06, 2004 12:44 am
Location: Brazil
Contact:

10047 Help

Post by Renato » Wed Oct 06, 2004 12:48 am

Can anyone give me some ideas to solve this problem? Is this a graph problem, or geometric? Please help.
Renato Ferreira

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

Post by jambon_vn » Thu Oct 07, 2004 7:27 am

As I think, this is a graph problem and you can use BFS to solve.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

10047

Post by asif_rahman0 » Fri Jul 21, 2006 6:41 am

hello everybody,

i am having problem in description to get the idea. i dont get the following
lines:

Code: Select all

From any square either he moves forward to the next square or he remains in the same square but turns 90o left or right. Each of these actions requires exactly 1 second to execute. He always starts his ride facing north and with the mid

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Jul 21, 2006 8:13 am

Turning 90 degrees left means that you change north direction to west; west->south; south->east; east->north. In other words, if your direction vector is (dx, dy), then the new vector will be (-dy, dx).
Your position doesn't change.

Turning right is the opposite thing (north->east, east->south, etc.)

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Fri Jul 21, 2006 5:03 pm

thnx mf.:)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10047 - The Monocycle

Post by DD » Sat Nov 15, 2008 6:12 am

Farid Ahmadov wrote:Hey People. Help. Won't anybody help me? :cry:
Maybe you can list your codes, and let us examine it for you.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10047 - The Monocycle

Post by kbr_iut » Fri Jan 09, 2009 3:02 pm

I tried a lot of times and generate many test cases and compare the output with uvatoolkit and mine but didnt fine any inconsistent......I am getting frequent WA...pliz anyone help.

Code: Select all

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define sz 30
#define inf 1<<30
const int X[4]={0,-1,0,1};
const int Y[4]={-1,0,1,0};
typedef struct st{int x,y,c,d;};
st v,var;
int tem,cost[sz][sz][4][5],x,y,t,txt,m,n;
char in[sz][sz];
bool check(){
	tem=cost[v.x][v.y][v.d][v.c];
	if(cost[var.x][var.y][var.d][var.c]<=tem+1)return false;
	cost[var.x][var.y][var.d][var.c]=tem+1;
}
bool forward(){
	var=v;
	var.x+=X[var.d];
	var.y+=Y[var.d];
	if(var.x>=m||var.x<0||var.y>=n||var.y<0)return false;
	if(in[var.x][var.y]=='#')return false;
	var.c=(var.c+1)%5;
	if(!check())return false;
}
bool left(){
	var=v;
	var.d=(var.d+3)%4;
	if(!check())return false;
}
bool right(){
	var=v;
	var.d=(var.d+1)%4;
	if(!check())return false;
}
int main(){
	int i,j,k,l,ans;
	//freopen("1.txt","r",stdin);
	while(cin>>m>>n&&(m||n)){
		for(i=0;i<m;i++){cin>>in[i];for(j=0;j<n;j++)if(in[i][j]=='S')v.x=i,v.y=j;}
		queue<st>q;
		v.c=1;v.d=1;
		for(i=0;i<sz;i++)for(j=0;j<sz;j++)for(k=0;k<4;k++)for(l=0;l<5;l++)cost[i][j][k][l]=inf;
		cost[v.x][v.y][v.d][v.c]=0;
		q.push(v);
		ans=inf;
		while(!q.empty()){
			v=q.front();q.pop();
			if(in[v.x][v.y]=='T'&&v.c==1){
				ans=cost[v.x][v.y][v.d][v.c];
				break;
			}
			if(forward())q.push(var);
			if(left())q.push(var);
			if(right())q.push(var);
		}
		if(txt++)cout<<endl;
		if(ans>=inf)cout<<"Case #"<<txt<<"\ndestination not reachable\n";
		else cout<<"Case #"<<txt<<"\nminimum time = "<<ans<<" sec\n";
	}
	return 0;
}

any help will be regarded gratefully.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

arash16
New poster
Posts: 1
Joined: Fri Jan 16, 2009 10:13 am

Re: 10047 - The Monocycle

Post by arash16 » Fri Jan 16, 2009 10:16 am

Sample Input:

Code: Select all

5 10
.S........
..##.....#
..#...T...
..#.......
..#.......
15 15
S......#.......
.......#.......
......#.#....T.
......#..#.....
.....#...#.....
....#.....#...#
....#.#.#.#....
....#..#...#...
...#..##.#.#...
...#...#....#..
..#..#.#....#..
..#.#..#.....#.
.##..#.#.....#.
...#...#.....#.
#......#.......
1 10
.S.....T..
1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
5 5
#S#..
#.#..
#.###
#...T
#####
10 10
S.........
..........
..........
..........
..........
..........
..........
..........
..........
........T.
3 3
ST#
##.
.#.
6 6
#.#...
#.S.#.
#####.
#..#..
#T##..
......
0 0
Sample Output:

Code: Select all

Case #1
minimum time = 19 sec

Case #2
minimum time = 82 sec

Case #3
minimum time = 13 sec

Case #4
destination not reachable

Case #5
minimum time = 49 sec

Case #6
minimum time = 17 sec

Case #7
minimum time = 30 sec

Case #8
minimum time = 14 sec

Case #9
minimum time = 30 sec

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10047 - The Monocycle

Post by kbr_iut » Fri Jan 16, 2009 1:02 pm

thanx "arash16" for ur kind help.
but unfortunately my WA code produces same output.
I tested with a lot of randomly generated cases and compared with uvatoolkit.com.but in every case i got same output.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Post Reply

Return to “Volume 100 (10000-10099)”