A. Guilty — to the kitchen!

Suppose that the maximum volume is x, and then we can derive several inequalities that x should satisfy.

1) For each index i, x*a[i]/(a[1]+a[2]+a[3]+...a[N])<=b[i], where "/" means float division;

2) x<=V

Therefore, x=min(V, min(b[i]*(a[1]+a[2]+a[3]+...a[N])/a[i]) )=min(V, (a[1]+a[2]+a[3]+...a[N])*min(b[i]/a[i])). This implies that we can first find out the minimum value of b[i]/a[i], and then the answer is straightforward.

B. Game of chess unfinished

For each rook, we can calculate the positions that it can take. Note that the white king (or another rook) might serve as an obstacle and thus "protect" some positions from being taken by the current rook, even though these positions lie in the same row or column as the rook. For instance, consider a rook with "b2" and a white king with "b4", in which case all positions with "b5,b6,b7,b8" cannot be taken by this rook (however they may be taken by another rook or the white king). Similarly, we can obtain the positions that the white king can take as well.

Now, we can first check whether the white has checkmated the black. Then, we move the black king to the eight adjacent positions (if these positions are reasonable), and check whether it will be taken by the white or not. As long as there exists one sinlge position at which the black king can avoid being taken by the white, the answer is "OTHER". Note that one of the white rooks might be taken by the black king, as the problem says.

C. Safe cracking

Well, this is a somewhat weird problem...

A feasible solution is shown as follows:

1) if all the four integers are reduced to 1, stops; otherwise go to step 2);

2) find out the maximum integer a[max_n] and denote its left and right integer as a[L] and a[R], respectively. Then, select one of the following branches to implement:

A) a[max_n]%2=0: if at least one of a[L] and a[R] is an even integer, divide it and a[max_n] by 2 (if they are both even integers, we can select the larger one); if both of them are odd integers, increase the larger one and a[max_n] by 1; after this, go to step 1);

B) a[max_n]%2=1: if at least one of a[L] and a[R] is an odd integer, increase it and a[max_n] by 1 (if they are both odd integers, we can select the larger one); if both of them are even integers, increase the larger one and a[max_n] by 1; after this, go to step 1);

In genreal, for a given integer N, by dividing it by 2, it takes us log(N) times to reduce it to 1. However, sometimes the intermediate result may turn out to be an odd integer and it might take 3 more times to go on with division. For instance, a[L] is even; a[max_n] is odd; a[R] is even. Therefore, it takes 4*(3*log(N)) operations, which is about

4*(3*log(10^9))<=12*log((2^4)^9)=12*36=432<1000

D. Strange town

I was inspired by the other solutions. Suppose that we assign an integer a[i] to node with index i. Then, for two nodes i and j, if we assign a value a[i]+a[j] to the edge between node i and node j, one can check that for any Hamilton cycle, the total value will always be 2*(a[1]+a[2]+...a[N]), which just meets the request in the problem. Therefore, the problem is solved if we can guarantee that there exists no a[i]+a[j] that is equal to any other a[s]+a[t]. Specifically, we can adopt the "hash idea" to record all the values of a[i]+a[j] that have been appeared for the first N-1 nodes, and for the N-th node, we can enumerate from 1 to 1000 to select an appropriate integer for a[N], which leads to no contradiction, and finally update the "hash table" for the newly added a[N].

Well, this is really a wonderful solution which transforms the original problem into a simpler one, but how could the first person come up with such an idea.....