spend two days to solve drunk king problem...using divide and conquer...

there are 5 problems left, welcome to discuss each other...

now I sort the problem difficult for me

1589>1394>1388>1999>1596

seems 1999 is harder than 1596???

oh I know how to solve knight problem now....

there are four problems left and I know how to solve ural 1388 now:

suppose the slop of line on the x>0 is k ,and slope of (0,0) to n

points is k1,k2,...kn then intersection point of x1==1/(k1-k),x2=1/(k2-k)...xn=1/(kn-k)

then we choose (x4-x1)/(x2-x1)==(x4'-x1')/(x2'-x1') and (x3-x2)/(x3-x4)==（x3'-x2'）/(x3'-x4')

we multiply these two equations guess what happens, yes: k is offset

then we can get (k4-k1)*(k3-k2)/((k2-k1)*(k3-k4))==(k4'-k1')*(k3'-k2')/((k2'-k1')*(k3'-k4'))

en.. this convert to string matching prolems,so suffix array can solve it

btw anyone has ideas of ural 1999 ural 1394 and ural 1589???

ural 1394 I got TLE on test 70, it is so hard!!!

ural 1394 I got AC hahaha

7657892 17:46:50 5 Dec 2017 Shen Yang 1394. Ships. Version 2 Visual C++ 2017 Accepted 0.904 59 064 KB

I think ural 1589's AC will be sooner or later, at least I can use my hand to binary search the test when get stuck

ural 1589 AC:

7660985 12:12:33 7 Dec 2017 Shen Yang 1589. Sokoban G++ 7.1 Accepted 4.321

58 056 KB

solve all ural problems is a question of time