Homework 01 Solution

Description
Dr. Abagale Xenovian, a reclusive mathematician and master of games, has found a potentially valuable exploit in her favorite video game. When she uses a special attack combination, one of two things happen:

1. If her score is even, she loses 99 points and then her score is multiplied by 3.

2. If her score is odd, she loses 15 points and then her score is multiplied by 2.

Note that all scores are limited to a max value of 1,000,000. Any score that hits that limit will immediately loop back around (so a score of 1,000,007 just becomes a score of 7). Likewise, any score that goes below zero ALSO loops around (so a score of -7 would become a score of 999,993).

Given a starting score ( S ) and a number of times the exploit is used ( k ), determine Dr. Xenovian's final score in the game.

Input Format

The first line is a number ( T ), indicating the number of test cases. The next T lines each have two values, S and k, indicating the starting score and the number of times the exploit is used, respectively.

Constraints

1 ≤ T ≤ 100
0 ≤ S ≤ 1,000,000
0 ≤ k ≤ 100
Output Format

T lines, each indicating the final score in the associated game.

Example 0
Sample Input

3
1000 1
1000 2
1000 5
Sample Output

2703
5376
94599


escription
Extinction is a complex card game involving betting. In the final phase of the game, each round players must bet the amount of money that the poorest player has remaining. When someone is out of money, they drop out of the game. Play continues until only one player remains.

Dr. Xenovian plays in an Extinction tournament. Assuming she starts the final phase of the game with the most money and wins every round, can you track how many of her opponents will remain each round?

Suppose Dr. Xenovian has six opponents with the following amounts of money left (in thousands of dollars):

5 4 4 2 2 8

Then, in the first round, should would bet $2,000, which will bankrupt two of the players. For the next round, four opponents are left with the following amounts of money:

3 2 2 _ _ 6

The above step is repeated until no opponents are left.

Input Format

The first line contains a single integer N indicating the number of opponents.

The next line contains N integers: a0 , a1 , ..., aN-1  separated by spaces, where a represents the amount of money that the i th player has.

Constraints

1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000
Output Format

For each pass, print the number of opponents that remain.

Example 0
Sample Input

6
5 4 4 2 2 8
Sample Output

6
4
2
1



Description
Dr. Xenovian is playing a game where there are two possible moves each turn, one that earns a player x points and the other earns the player y points. The winner is the player closest to a given target score after n moves.

Given x, y, and n, can you calculate the set of all possible scores at the end of the game?

Input Format

The first line contains an integer T indicating the number of test cases.

The next T lines each describe a test case with three integers: x, y, and n.

Constraints

1 ≤ T ≤ 10
1 ≤ x, y, n ≤ 1000
Output Format

Space-separated list of numbers which are the possible total scores in increasing order.

Example 0
Sample Input

2
1 2 2
10 100 3
Sample Output

2 3 4
30 120 210 300



Description
Dr. Xenovian has many ideas for designing new board games. After she tries a set of new games, she also comes up with ways of merging those games to explore more possibilities. How many total new games can she make?

During each brainstorming session, Dr. Xenovian starts with n different ideas. She groups these into sets of m ideas to design each game. After that, for every c games she designs and plays, she can combine those games into yet one more game.

For example, assume she starts with n=4 ideas, plans to use only one new idea for each game (m = 1), and for every two games she plays, she will generate ideas for one new game idea (c = 2). Dr. Xenovian can design 4 games with her initial ideas, and then (after playing those games) comes up with 2 new games. When those new games finish, she can use them to generate yet another 1 game, for a grand total of 7 games ever.

Input Format

The first line contains a single integer T indicating the number of test cases.

The next T lines each have three integers, separated by spaces, indicating n, m, and c for that test case.

Constraints

1 ≤ T ≤ 1000
2 ≤ n ≤ 105
1 ≤ m ≤ n
2 ≤ c ≤ n
Output Format

For each test case, print the number of games that can be created during that brainstorming session.

Example 0
Sample Input

3
10 2 5
12 4 4
6 2 2
Sample Output

6
3
5

Description
Dr. Xenovian has developed a fantastic new computer game, but it requires a new type of multi-core computer that she designed. The cores in this computer must come in multiples of 12 AND they must be arranged on the motherboard in a perfect square.

Atfter talking to each customer, Dr. Xenovian determines the minimum number of cores they need ( x ) and the maximum number of cores they can afford ( y ). Given this range in the number of cores possible, she then needs to calculate how many of these values are divisible by 12 (d ), how many are perfect squares ( s ), and how many values have both qualities ( b ).

Write a program to perform these calculations.

Input Format

The first line contains C, the number of customers she needs to perform calculations for. C ranges then follow, each on a new line.

Each test contains two space-separated integers denoting the MIN( x ) and the MAX( y ) number of cores, inclusive.

Constraints

1 ≤ C ≤ 100
1 ≤ x ≤ y ≤ 109
Output Format

With each customer result on a new line, print out d, s, and b (where d is the number of values divisible by 12, s is the number of perfect squares, and b is the number of values that meet both criteria).

Example 0
Sample Input

2
6 12
25 37
Sample Output

1 1 0
1 2 1


Description
Dr. Xenovian has come up with an even better layout for the cores in her new computer system. This time, though, her specialized architecture requires that the cores are divided into two processing units, a CPU and an IPU (intelligence processing unit), each of which must be arranged in a PLUS shape. These pluse-shaped processing units have to be placed to avoid the other components on the motherboard. Can you help her figure out how big to make them?

You are given a grid of size N-by-M representing the motherboard. Each cell on this grid is either a good or bad place to put a core.

Each processing unit must be shaped like a plus sign on a grid. A valid plus has a horizontal line of cells and a vertical line of cells of equal lengths and crossing in the middle.

The overall processing speed is the number of cells in the CPU times the number of cells in the IPU. You must calculate the maximum processing speed.

Input Format

The first line contains two space-separated integers, N and M.

The N subsequent lines each contain M characters, where each character is either G (a good place to put a core) or B (a bad place to put a core).

 Constraints

2 ≤ N ≤ 15
2 ≤ M ≤ 15
Output Format

 Output the maximum production level.

Example 0
Sample Input

5 6
GGGGGG
GBBBGB
GGGGGG
GGBBGB
GGGGGG
Sample Output

5

Description
Dr. Xenovian's specialized computer architecture has taken off (it turns out that is really well-suited for mining gigabyte coins), and her technical prowess has caught the attention of RUST Corp., an interplanetary mining company. RUST Corp. has hired Dr. Xenovian to "consult on a TOP SECRET hardware problem". After signing a non-disclosure agreement, Dr. Xenovian is flown to a high-security warehouse in Olympus City that is filled with alledgely-alien monoliths of all different shapes and sizes that RUST Corp. has collected during their mining expeditions.

Each monolith has matrix of integer values, and every 36 seconds, the values rotate in an anti-clockwise direction on the monolith's surface as shown in the example below.



Note that in one rotation, elements shift by one step only. The first step to decoding these mysterious monoliths is to write a program capable of predicting the state of a matrix after an arbitrary number of rotations ( r ). Your task is to write this program.

All monolith-matrices are such that the minimum of m and n will be even.

As an example, rotate the Start matrix by 2:

Start         First           Second
 1 2 3 4       2  3  4  5      3  4  5  6
12 1 2 5  =>   1  2  3  6 =>   2  3  4  7
11 4 3 6      12  1  4  7      1  2  1  8
10 9 8 7      11 10  9  8     12 11 10  9
Function Description

Complete the monolithRotation function. It should print the resultant 2D integer array and return nothing.

monolithRotation has the following parameters:

matrix: a 2D array of integers
r : an integer that represents the rotation factor
Input Format

The first line contains three space-separated integers, m, n, and r (rows, columns, and rotations respectively).

The next m lines contain n space-separated integers, representing the elements of a row of matrix.

Constraints

2 ≤ m, n ≤ 300
1 ≤ r ≤ 109
min(m,n) % 2 = 0
1 ≤ aij ≤ 109 where i ∈ [1...m] and j ∈ [1...n]
Output Format

Print each row of the rotated matrix as space-separated integers on separate lines.

Example 0
Sample Input

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Sample Output

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14
Explanation

The matrix is rotated through two rotations.

 1  2  3  4      2  3  4  8      3  4  8 12
 5  6  7  8      1  7 11 12      2 11 10 16
 9 10 11 12  ->  5  6 10 16  ->  1  7  6 15
13 14 15 16      9 13 14 15      5  9 13 14
Example 1
Sample Input

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28
Sample Output

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1
Explanation

The various states through 7 rotations:

1  2  3  4      2  3  4 10    3  4 10 16    4 10 16 22
7  8  9 10      1  9 15 16    2 15 21 22    3 21 20 28
13 14 15 16 =>  7  8 21 22 => 1  9 20 28 => 2 15 14 27 =>
19 20 21 22    13 14 20 28    7  8 14 27    1  9  8 26
25 26 27 28    19 25 26 27    13 19 25 26   7 13 19 25

10 16 22 28    16 22 28 27    22 28 27 26    28 27 26 25
 4 20 14 27    10 14  8 26    16  8  9 25    22  9 15 19
 3 21  8 26 =>  4 20  9 25 => 10 14 15 19 => 16  8 21 13
 2 15  9 25     3 21 15 19     4 20 21 13    10 14 20  7
 1  7 13 19     2  1  7 13     3  2  1  7     4  3  2  1
Example 2
Sample Input

2 2 3
1 1
1 1
Sample Output

1 1
1 1
Explanation