A. Extra-terrestrial Intelligence

As the size n is no larger than 100, we can adopt a "vector" to record the indices of "1" which appear in the given sequence. Then, we calculate the difference between every two neighbouring indices, and if they are the same, the answer is "YES"; otherwise is "NO".

B. Fractal

This problem reminds me of Kronecker Product, which is often mentioned in the theory of matrix. In fact, this problem just asks to simulate the operation of Kronecker Product as far as I consider. For the first provided example, if we replace '.' with integer "1" while '*' with integer "0", we will obtain a matrix [1 0 ; 1 1]. If you are familiar with Matlab, you can use the function "kron" to calculate the finla matrix, and by mapping "1" and "0" back to '.' and '*', you will find that it is just the answer!! This conclusion holds for all values of n and k.

D. New Game with a Chess Piece

This is a rather complicated problem...

We might need do some pen and paper work to find out some principles hidden behind the game. We can start from the right bottom point, and consider the result if one should start moving from this point. For simplicity, we use 'L' and 'W' to denote that one loses and wins, respectively, if he starts from some point, and we use an array R[n][m] to record the results.

At first, we consider the case where k>1. Obviously, R[n-1][m-1]='L', and R[n-1][m-2]='W',R[n-1][m-3]='L'. This means that for the (n-1)-th row, 'L' and 'W' appear alternatively, and similarly one will find that for the (m-1)-th column, 'L' and 'W' appear alternatively as well. Then, we consider what happens in the (n-2)-th row. One will find that R[n-2][m-2]='L' since only R[n-1][m-2]=R[n-2][m-1]='W' can be reached from this point, i.e., the next person who moves will win. By some careful deduction, one will find that 'L' and 'W' appear alternatively for the (n-2)-th row and (m-2)-th column. In fact, this holds from the (n-1)-th row to the (n-k)-th row. For the (n-k-1)-th row, we can find that it is always 'W' from R[n-k-1][0] to R[n-k-1][m-k-1]. From the (n-k-2)-th row to the (n-(2*k+2))-th row, 'L' and 'W' appear alternatively again. In fact, we will find that from the (n-(2*k+2+1))-th row, the same pattern as that starts from the (n-1)-th row repeats. Therefore, we can calculate min(n,m)%(2*k+2) and find out which row between the (n-1)-th one and the (n-(2*k+2))-th it belongs to, and select 'L' or 'W' according to whether |n-m| is even or odd.

Then, we consider the case that k=1, which is quite similar to k>1. We also start from the (n-1)-th row and find out the corresponding pattern, and then move up to the upper row until we find that the same pattern starts to repeat.