11852 - Knight's Trip

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

Moderator: Board moderators

Post Reply
Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

11852 - Knight's Trip

Post by Nursoltan_h » Mon Oct 04, 2010 4:52 pm

Hi,
Any Hints How to solve this problem?

http://uva.onlinejudge.org/contests/263 ... 11852.html

Thanks in Advance

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11852 - Knight's Trip

Post by Angeh » Mon Oct 04, 2010 11:09 pm

A Pure Greedy algorithm will solve it ...
generate the output for a Board n*n and by induction find the solution to (n+1)*(n+1)
the minimum number of moves are at least the (x+1)/2 , and also at least (y+1)/2 since you can more at most 2 row or column each time ... and the total of 3 cells each time .... so the number of moves is also at least (x+y+2) /3 ....
we suppose that cell 0,0 is colored white ...
so if the target cell is also white we need even number of moves ...
else if target cell is black we need odd number of moves ...
there are 4 cells in the Board that dont use the Principle mentioned above and you need to check this cases ...
now its easy to find the solution ...

you can find usefull hints for this kind of Problems in Algorithmic problem solving book .......
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11852 - Knight's Trip

Post by Nursoltan_h » Tue Oct 05, 2010 1:04 pm

Thank you very much.

jurong
New poster
Posts: 6
Joined: Wed Oct 06, 2010 1:05 pm

Re: 11852 - Knight's Trip

Post by jurong » Wed Oct 06, 2010 1:10 pm

Thanks for your help.
But can you tell me where to download "Algorithmic problem solving book"?
I looked at google but cannot find.
Thank you again.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11852 - Knight's Trip

Post by Igor9669 » Thu Oct 07, 2010 12:32 pm

You could find it here: http://uvatoolkit.com/material.php

jurong
New poster
Posts: 6
Joined: Wed Oct 06, 2010 1:05 pm

Re: 11852 - Knight's Trip

Post by jurong » Thu Oct 14, 2010 8:33 am

Thanks Igor9669.
Following your link I found this course by the author but I cannot download the book (maybe this link is not avaiable).
If you have this book, can you sent to me via my email : doulce2000@yahoo.com.
Thanks you much!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11852 - Knight's Trip

Post by Angeh » Thu Oct 14, 2010 10:38 am

sent
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 11852 - Knight's Trip

Post by sir. manuel » Thu Sep 08, 2011 5:40 am

i search it in the internet but i can´t find it!!!, so please can you send it to my email????....kavic1@hotmail.com


Thanks

Post Reply

Return to “Volume 118 (11800-11899)”