Facebook Hacker Cup 2011 Round 1 B
Slot Machine Hacker
You recently befriended a guy who writes software for slot machines. After hanging out with him a bit, you notice that he has a penchant for showing off his knowledge of how the slot machines work. Eventually you get him to describe for you in precise detail the algorithm used on a particular brand of machine. The algorithm is as follows:
int getRandomNumber() {
secret = (secret * 5402147 + 54321) % 10000001;
return secret % 1000;
}
This function returns an integer number in [0, 999]; each digit represents one of ten symbols that appear on a wheel during a particular machine state.secret is initially set to some nonnegative value unknown to you.
By observing the operation of a machine long enough, you can determine value of secret and thus predict future outcomes. Knowing future outcomes you would be able to bet in a smart way and win lots of money.
Input
The first line of the input contains positive number T, the number of test cases. This is followed by T test cases. Each test case consists of a positive integer N, the number of observations you make. Next N tokens are integers from 0 to 999 describing your observations.
Output
For each test case, output the next 10 values that would be displayed by the machine separated by whitespace.
If the sequence you observed cannot be produced by the machine your friend described to you, print “Wrong machine” instead.
If you cannot uniquely determine the next 10 values, print “Not enough observations” instead.
Constraints
T = 20
1 ≤ N ≤ 100
Tokens in the input are no more than 3 characters long and contain only digits 0-9.
sample input
5
1 968
3 767 308 284
5 78 880 53 698 235
7 23 786 292 615 259 635 540
9 862 452 303 558 767 105 911 846 462
sample output
Not enough observations
577 428 402 291 252 544 735 545 771 34
762 18 98 703 456 676 621 291 488 332
38 802 434 531 725 594 86 921 607 35
Wrong machine
Chess 2
After decades of shadowy demonstrations and delays from the game’s maker, Chess 2 has finally been released. You waited in line all night to be one of the first to purchase an example of the hot sequel to the classic original, and now you are finally getting a chance to open up your new investment and take a look inside. What you find is slightly puzzling; in addition to the traditional pieces, the game has been expanded to contain a number of pieces that are not actually original.
]
The best-known piece that has been added to the game is the nightrider. The nightrider can make any number of knight moves in a single direction, i.e., its offset from its initial position will be 2*m in one dimension and m in the other for some nonzero integer m. Like other “sliding” pieces, if one of the knight moves would cause it to take another piece it is not able to traverse beyond that point
The archbishop is also part of Chess 2. The archbishop can simply make any move that a knight or bishop could legally make.
The strangest new piece is the kraken. The kraken can move to any square on the board, regardless of the position of any other pieces, including its own current position.
You don’t feel like reading the manual to learn about how the new pieces fit into the standard chess opening positions, so instead you place some of the pieces randomly on the board. The game you’ve decided to play is simply to count how many pieces on the board are currently being threatened. A piece is threatened if another piece is able to move into its cell and take it (note that if the kraken moves into its own cell it does not take itself).
Input
Your input file will consist of a single integer N followed by N test cases. Each case will consist of, all separated by whitespace, an integer P followed by the identities and positions of P Chess 2 pieces. Pieces are described by a single character C to denote their type (see specification below) followed by two integers R and F, the 1-based rank and file, respectively, of the piece.
You’ve decided to ignore the colors of the pieces in this game. The color of the pieces will not be reflected in the input and so cannot affect your output.
To make room for the new pieces, the Chess 2 board is a 16 by 16 grid. No specified pieces will fall outside the board, and no two pieces will occupy the same position.
The types of pieces will be specified as follows, and no entries not present in this table will appear on the board:
| Piece | Abbreviation |
| King | K |
| Queen | Q |
| Rook | R |
| Bishop | B |
| Knight | N |
| Nightrider | S |
| Archbishop | A |
| Kraken | E |
Output
Output a single integer, the number of threatened pieces on the board, for each test case separated by whitespace.
Constraints
N = 20
3 <= P <= 64
1 <= R, F <= 16
C will be one of K, Q, R, B, N, S, A or E
sample input
5
4 Q 1 1 B 3 1 B 5 1 B 1 4
3 S 1 1 K 2 3 S 3 5
4 N 1 1 B 3 3 Q 5 5 N 4 1
5 R 2 2 N 1 2 N 2 1 N 16 2 N 2 16
6 Q 1 1 Q 2 3 Q 3 5 Q 4 2 Q 5 4 E 1 5
sample output
2
1
3
4
6
Diminishing Circle
N people are standing in circle and play following game: they start with the first person, count K people clockwise, then the K+1-th person leaves the circle and the process starts all over, using the person clockwise of the last person removed as the starting point.
For example when N = 9 and K = 3 people would leave in following order: 4, 8, 3, 9, 6, 5, 7, 2
Given N and K, find who wins the game if counting starts with person 1. Person indices are 1-based.
The last person who is left is declared the winner.
Input
The input consists of a single integer T, the number of test cases. This is followed by T pairs of numbers N and K, all separated by whitespace.
Output
Print T whitespace-separated integers, the indices for each test case of the winner of the game.
Constraints
T = 20
1 ≤ N ≤ 1012
1 ≤ K ≤ 104
sample input
5
9 3
4 1
3 2
5 4
6 9
sample output
1
1
2
2
2
]
