A
brute force max(x,y)/min(x,y) then just do it
B
because of t only 50000,the length of side of final board wont be very large make a table then you can find the length of side <=60.So brute force
C
every time choose two vector u v that d[u]=A[u]-B[u]>0 && d[v]=A[v]-B[v]<0 find a flow from u to v.obviously after that at least one d of u v will be 0 (d[u]==0||d[v]==0) also one work will use no more than n edges one work at least fit one vector's meet,there are n vector,So the total number is less than n*n
D define base number is the number can not be other number's power(like 2 3 6 but not 4 16) define base set is the set of one base number's power obviously,every base set is independent so we only care about the SG of every set (NIM game) then we consider two sets’ total number of elements are same (card(A)=card(b))
if we y is x's power we build a edge between x y then we can find if two set's size is same then the edge are also same maximum is log(10^9)<30 so question is to find SG(0) SG(1)... SG(29) how to calculate SG(x)? x<=30 brute force! last calculate all base set's size and xor
E very interesting! first if m==0 of course -1 if m==1 easy to find a way m>1 case 1: there is not a path connected s t
It mean somes tree surround s or some trees surround t So you can not put s t into same cell
case 2: there is a path connected s t in this case solution will always exist our strategy is princess follow the shortest path shortest path gives princess a queue of the steps that she should perform. Addition if shadow moves, then we add her move to the queue. In our strategy firstly we can find the distance between princess and her shadow will no-increase.
case 2.1
if in a time the distance between princess and her shadow decrease to 0 then that's the way
case 2.1
if the distance awalys >0
in this case we consider the left-most tree as tl and right-most tree tr.
if the distance still >0 after a long time we can imagine that princess and her shadow will go far away from all the tree.
draw a small graph(X-axis)
there are only four possibilities
(1)princess-shadow-tree
(2)shadow-princess-tree
(3)tree-princess-shadow
(4)tree-shadow-princess
(2)(3) transform to (4)(1) by using operator[UUUUUU...LLLLLLL...(orRRRRRR...)DDDDDDDD....]
in possibility (1) we can use tree tl to catch shadow
in possibility (2) we can use tree tr to catch shadow(this two just like m==1)so whole problem be solved
