Page 1 of 1
605 - The Rotating Disk
Posted: Thu Jun 05, 2003 8:11 am
by Miguel Angel
How to solve it?. I can think about Greedy, but some cases my heuristhics don't work. Or search, but won't be too large store partial permutations?
Re: 605
Posted: Tue Jul 01, 2003 10:10 am
by Alexander Denisjuk
Miguel Angel wrote:How to solve it?. ?
Well, just analyse the problem to see when it is soluable, when it is not. If yes, my algorithm is to place all the numbers to their places, one by one.
A propos, does anybody know if there is any problem, which can be solved by using some heuristics?
605 - The Rotating Disk...limit for n?!?
Posted: Thu Jan 22, 2004 1:42 am
by Subfallen
I have two doubts regarding 605.
(1) Is there supposed to be a limit for n? It is not given in the problem!
(2) Does anyone know a deterministic approach for converting a set of numbers to natural order? I have not been able to think of a way, and am about to attempt a heuristic search
605 ???
Posted: Mon Feb 21, 2005 11:07 pm
by Shit
Excuse me, but there is small problem in this problem
Please tell me why
the code
#include <stdio.h>
void main()
#include <stdio.h>
void main()
{
int a;
scanf("%d",&a);
while (a)
{
printf("%d",a);
scanf("%d",&a);
}
}
gives me
Time Limit Exceeded 0:10.064
, but not a wrong answer ??
Posted: Mon Feb 28, 2005 2:49 pm
by emotional blind
the loop
while(a){
...
}
continues untill a==0
but the input does not contain any zero
so your loop doesnt end
and you get TLE
Posted: Thu Mar 17, 2005 2:49 pm
by little joey
Yes, the problem is slightly under-specified.
(1) I use 4 <= n <= 256.
(2) It doesn't state that the solution has to be optimal. My algo performs < 4*n*n steps worst case, but significantly less on average. I don't know what the output limit is, but I suppose it's not too difficult to write a program that reaches it.
605
Posted: Sun Aug 14, 2005 3:31 am
by Yu Fan
in this problem,how can we detemine whether the track can be solved?
thanks in advance
Re: 605
Posted: Sun Aug 24, 2008 5:28 pm
by christephan
Yu Fan wrote:in this problem,how can we detemine whether the track can be solved?
thanks in advance
You can write another programme to find out when the track can be solved.
Re: 605 - The Rotating Disk
Posted: Tue Oct 19, 2010 10:24 am
by stencel
I'm still fighting the prob and cannot get accepted. Could someone please share with me some clarifications of the tasks? The description is rather vague.
1. What is "the natural order"? Is the reverse "3 2 1" natural?
2. How do you understand "You must not display moves around the whole
track."? Ain't we allowed to do anything when N == 4 or we are allowed
but we are supposed not to print it?
3. Could someone please show me your correct output for the test case below?
4. Do you know about other nasty traps in this problem description?
Code: Select all
1
1 2
2 1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
5 4 3 2 1
6 5 4 3 2 1
7 6 5 4 3 2 1
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
EDIT: I finally got AC Here are the answer (from email from Cedric Lin; thanks!):
1. "natural order" is just increasing order, I believe. So "3 2 1" is not natural.
2. I think what is meant by "moves around the whole track" are moves that would wraparound the output line. (So you can't have "1 2* 3 4 5 6 7 8 *9 10" to indicate that you are rotating the disk with 9, 10, 1 and 2.)
Code: Select all
1
1 2
2 1
1 2 3
1 3 2
It is not possible to rearrange these disks in natural order.
2 1 3
It is not possible to rearrange these disks in natural order.
2 3 1
3 1 2
3 2 1
It is not possible to rearrange these disks in natural order.
1 2 3 4
1 2 4 3
It is not possible to rearrange these disks in natural order.
1 3 2 4
It is not possible to rearrange these disks in natural order.
1 3 4 2
It is not possible to rearrange these disks in natural order.
1 4 3 2
*2 3 4 1*
1 4 2 3
It is not possible to rearrange these disks in natural order.
5 4 3 2 1
*2 3 4 5* 1
6 5 4 3 2 1
5 4 *6 1 2 3*
*1 6 4 5* 2 3
1 *2 5 4 6* 3
1 2 *3 6 4 5*
*6 3 2 1* 4 5
6 3 *5 4 1 2*
6 *1 4 5 3* 2
6 1 *2 3 5 4*
*3 2 1 6* 5 4
3 *5 6 1 2* 4
*1 6 5 3* 2 4
1 *2 3 5 6* 4
*5 3 2 1* 6 4
5 3 *4 6 1 2*
5 *1 6 4 3* 2
5 1 *2 3 4 6*
*3 2 1 5* 4 6
3 *4 5 1 2* 6
*1 5 4 3* 2 6
1 *2 3 4 5* 6
7 6 5 4 3 2 1
It is not possible to rearrange these disks in natural order.
8 7 6 5 4 3 2 1
8 7 6 5 *1 2 3 4*
8 7 *2 1 5 6* 3 4
*1 2 7 8* 5 6 3 4
1 2 *6 5 8 7* 3 4
1 2 6 5 *4 3 7 8*
1 2 *3 4 5 6* 7 8
BTW: I checked that there are no inputs with N < 4.