HCHAINS - Islands and Hotel Chains

no tags 

In Croatia there are N small islands. For the purposes of further tourism development, the government has decided to build exactly one hotel on the each island. The government has contracts with two hotel chains: let's call them A and B. Unfortunately, there is a problem since each hotel chain wants to build as many hotels as possible.

Thus, the following agreement has been made: the hotels will be built such that, for each horizontal or vertical line (that is, if we imagine the problem in the 2D coordinate system, for each line with the equation y = c or x = c), the absolute difference between the number of hotels (on that line) of the chain A and the number of hotels (on that line) of the chain B is at most 1.

Write a program that will, for each small island, determine the hotel chain (A or B) which will build the hotel on that island, such that the upper agreement holds.


In the first line of input there is an integer T, the number of test cases.

For each test case, in the first line there is an integer N, the number of islands.

In the next line there are eight integers: X(1), Y(1), Ax, Bx, Mx, Ay, By, My; each from the interval [1, 100 000], except for X(1) and Y(1) which are from the interval [0, Mx-1] and [0, My-1], respectively.

2D coordinates of the i-th island (for 2 ≤ i ≤ N) are:

X(i) = ( Ax * X(i-1) + Bx ) mod Mx;

Y(i) = ( Ay * Y(i-1) + By ) mod My.

It is guaranteed that no two islands will have the same position and the solution, not necessarily unique, will always exist.

Note: Author's solution doesn't depend on properties of pseudo-random generator.

Data set is divided into 2 parts:
     First part:     1 <= T <= 100, 1 <= N <= 5000
     Second part: 1 <= T <= 10, 1 <= N <= 100 000


For each test case, output in a separate line a string of size N, containing only the letters A and B. The i-th letter of the string denotes the hotel chain which will build the hotel on the i-th island.



2 4 8 2 5 6 9 5




The points in this example are:

2 4
3 3
1 2
0 1
2 0
3 4
1 3
0 2
2 1
3 0

hide comments
Aditya Muraletharan: 2013-04-20 12:41:10

Excellent Problem. Had great fun solving it:)

Added by:Ivan Katanic
Time limit:0.566s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:derived from the problem of International Mathematical Olympiad. prepared by I. Katanić, A. S. Kurdija and S. Glavina