11198 - Dancing Digits

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sunshine12
New poster
Posts: 3
Joined: Sun Dec 08, 2013 1:13 pm

Re: 11198 - Dancing Digits

Post by sunshine12 » Thu Dec 19, 2013 9:15 am

i still dont get it..

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

Re: 11198 - Dancing Digits

Post by brianfry713 » Fri Dec 20, 2013 2:47 am

http://en.wikipedia.org/wiki/Breadth-first_search
Suppose the initial digits are:
1 2 4 5 6 7 -3 8
Put the initial digits onto the queue and also keep track of the number of moves.

Pop the front of the queue
Iterate through all pairs of digits until you find a pair where one is positive and one is negative and the sum of the absolute values is prime. Those pairs are: 2 and -3, 4 and -3, -3 and 8.
For each pair, generate all the possible moves: female to the left of the male, female to the right of the male, male to the left of the female, male to the right of the female.
So for pair 2 and -3, the possible moves are:
1 -3 2 4 5 6 7 8 (-3 to 2's left)
1 2 -3 4 5 6 7 8 (-3 to 2's right, this one ends up sorted)
1 4 5 6 7 2 -3 8 (2 to -3's left)
1 4 5 6 7 -3 2 8 (2 to -3's right)
Put each new state to the end of the queue.
Do the same with the other pairs 4 and -3, -3 and 8
Continue until you reach a sorted state or the queue is empty
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 111 (11100-11199)”