Superking
TCO05 Finals · 2005-08-16 · by gepa
Problem Statement
We have an infinite chess board, and a new type of chess piece called a "superking". It can perform two types of moves:
- Type-1: the normal king move - i.e., a move to a neighboring square in any of the eight directions horizontal, vertical or diagonal.
- Type-2: a move two squares to the left, right, up or down.
The superking begins at some square in the infinite board and performs type1 Type-1 moves and type2 Type-2 moves. Return the number of possible squares that the superking can reach after performing these moves.
Constraints
- type1 and type2 will be between 0 and 100000000 (108), inclusive.
0 0 Returns: 1
No moves are made, superking remains at the starting square.
1 0 Returns: 8
After one Type-1 move (normal king move), the superking can land in one of the 8 neighboring squares.
0 1 Returns: 4
After one Type-2 move, the superking lands in one of the four squares at a distance of 2 from the starting square (to the left, right, up or down).
1 2 Returns: 60
Let's assume that the superking starts at the red square at the center of the board shown below. After one Type-2 move, the superking can land in one of the blue squares. After the second Type-2 move, the superking can land in one of the red squares. After a final Type-1 move, the superking can land in any square neighboring a red square, i.e., one of the green squares. These are the possible final landing squares for the king after 1 Type-1 and 2 Type-2 moves, 60 in total (note that it is not important in which order we make the moves; here, we first did the two Type-2 moves and then the Type-1 move).
31 17 Returns: 14713
100000000 100000000 Returns: 280000000400000001
The maximum return value.
Submissions are judged against all 56 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Superking with a public method long long squares(int type1, int type2) · 56 test cases · 2 s / 256 MB per case