SP8624 NY10B - Nim-B Sum

Note: This problem has nothing to do with siting sewage plants, power lines or wind farms. NIM is an ambigram. The game of NIM is played with any number of piles of objects with any number of objects in each pile. At each turn, a player takes one or more (up to all) objects from one pile. In the normal form of the game, the player who takes the last object is the winner. There is a well-known strategy for this game based on the nim-2 sum. The Nim-B sum (nim sum base _B_) of two non-negative integers _X_ and _Y_ (written _NimSum_(_B_, _X_, _Y_)) is computed as follows: 1. Write each of _X_ and _Y_ in base _B_. 2. Each digit in base _B_ of the Nim-B sum is the sum modulo _B_ of the corresponding digits in the base _B_ representation of _X_ and _Y_. For example: _NimSum_(2, 123, 456) = 1111011 ¤ 111001000 = 110110011 = 435 _NimSum_(3, 123, 456) = 11120 ¤ 121220 = 102010 = 300 _NimSum_(4, 123, 456) = 1323 ¤ 13020 = 10303 = 307 The strategy for normal form Nim is to compute the Nim-2 sum _T_ of the sizes of all piles. If at any time, you end your turn with _T_ = 0, you are guaranteed a WIN. Any opponent move must leave _T_ not 0 and there is always a move to get _T_ back to 0. This is done by computing _NimSum_(2, _T_, _PS_) for each pile; if this is less than the pile size (_PS_), compute the difference between the _PS_ and the Nim-2 sum and remove it from that pile as your next move. Write a program to compute _NimSum_(_B_, _X_, _Y_). Input ----- The first line of input contains a single integer _P_, (1_P_1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by three space separated decimal integers, _B_, _X_ and _Y_. 2_B_2000000, 0_X_2000000, 0_Y_2000000. Output ------ For each data set there is one line of output. It contains the data set number followed by a single space, followed by _N_, the decimal representation of the Nim sum in base _B_ of _X_ and _Y_. **Sample Input** 4 1 2 123 456 2 3 123 456 3 4 123 456 4 5 123 456 **Sample Output** 1 435 2 300 3 307 4 429

N/A

N/A