TopCoder Statistics - Problem Statement

Problem Statement

The (a,b)-knight is a chess piece that moves by jumping, just as a regular knight, but the jump is a cells in one direction, b in the other. Formally, an (a,b)-knight standing on the cell (x,y) can move to any of the following eight cells: (x+a,y+b), (x+a,y-b), (x-a,y+b), (x-a,y-b), (x+b,y+a), (x+b,y-a), (x-b,y+a), and (x-b,y-a). Of course, if the (a,b)-knight is close to the edge of the board, some of these cells might not be on the board. It is not allowed to jump to a cell that is not on the board.

A knight circuit is a sequence of cells on a chess board that starts and ends with the same cell. Each consecutive pair of cells in the knight circuit must correspond to a single jump of the (a,b)-knight. The knight circuit may visit each cell arbitrarily many times. The size of a knight circuit is the number of different cells visited by the circuit.

You are given the ints w and h: the width (in columns) and the height (in rows) of a rectangular chessboard. You are also given the ints a and b: the parameters of your knight. Return the maximum knight circuit size that can be obtained on the given board. You are free to choose any cell as the start of your circuit.

Definition

Class:: KnightCircuit
Method:: maxSize
Parameters:: int, int, int, int
Returns:: long
Method signature:: long maxSize(int w, int h, int a, int b)
(be sure your method is public)

Constraints

w, h will each be between 1 and 100000, inclusive.
a and b will each be between 1 and 10, inclusive.
a and b will not be equal.

Examples

1

1

2

1

Returns: 1

This is a 1x1 board. Note that a sequence that consists of a single cell is considered to be a valid knight circuit.
3

20

1

3

Returns: 11
100000

100000

1

2

Returns: 10000000000

It is possible to make a circuit that contains every cell on the board.
100000

20

1

2

Returns: 2000000
3

3

1

2

Returns: 8
30

30

8

4

Returns: 64
32

34

6

2

Returns: 136
3

13

1

6

Returns: 5
12

7

8

2

Returns: 4
16

14

5

10

Returns: 12
12

2

4

5

Returns: 1
8

14

9

1

Returns: 8
15

2

4

9

Returns: 1
3

10

6

4

Returns: 1
17

12

1

10

Returns: 180
5

14

5

2

Returns: 5
15

6

1

5

Returns: 45
15

20

2

9

Returns: 300
12

19

10

3

Returns: 114
20

13

3

8

Returns: 260
5

14

5

3

Returns: 3
13

15

10

5

Returns: 8
3

19

3

10

Returns: 1
12

14

6

8

Returns: 9
4

7

6

7

Returns: 1
10

13

7

5

Returns: 12
1

20

8

10

Returns: 1
11

8

5

6

Returns: 9
20

2

9

2

Returns: 1
9

6

6

2

Returns: 3
9

15

8

7

Returns: 5
14

3

9

5

Returns: 1
12

12

8

2

Returns: 32
19

7

8

7

Returns: 1
3

4

9

8

Returns: 1
13

2

3

1

Returns: 5
7

15

7

3

Returns: 5
12

16

6

10

Returns: 5
86573

11

9

2

Returns: 952303
19545

15

10

7

Returns: 107499
6

8596

9

2

Returns: 1434
6

44288

8

2

Returns: 8304
11

39919

10

5

Returns: 23952
2

86865

3

8

Returns: 1
7

19582

2

8

Returns: 4896
8

14173

7

1

Returns: 56692
4

56190

5

8

Returns: 1
7

28042

3

9

Returns: 4674
12

77212

5

7

Returns: 463272
15499

17

1

10

Returns: 263483
38540

1

7

8

Returns: 1
80907

8

8

1

Returns: 40456
15

98119

3

8

Returns: 1471785
25520

3

9

5

Returns: 1
21121

10

3

10

Returns: 4226
68414

13

10

7

Returns: 136828
26683

14

5

10

Returns: 16011
17

3722

2

9

Returns: 63274
32962

10

6

7

Returns: 131848
3

51991

9

7

Returns: 1
7

45344

10

1

Returns: 15873
13

87978

4

9

Returns: 1143714
2

54689

9

10

Returns: 1
3

70917

3

9

Returns: 1
98055

7

3

10

Returns: 14709
75676

9

9

3

Returns: 12614
16

22295

6

10

Returns: 44592
9

43800

6

5

Returns: 175200
88474

48377

6

9

Returns: 475587992
718

66834

7

4

Returns: 47986812
75710

7595

3

2

Returns: 575017450
28945

26410

10

1

Returns: 764437450
71102

98032

3

1

Returns: 3485135632
82215

27478

1

3

Returns: 1129551885
99361

98272

10

4

Returns: 2441125616
3379

76744

6

9

Returns: 28830914
95833

94992

8

5

Returns: 9103368336
95161

96832

7

2

Returns: 9214629952
98537

45833

6

4

Returns: 1129097673
24675

5416

8

7

Returns: 133639800
76917

750

6

10

Returns: 7211063
20509

39833

5

9

Returns: 408467499
22909

61815

8

4

Returns: 88520512
54396

26957

8

2

Returns: 366601842
74778

81236

5

2

Returns: 6074665608
78057

92319

2

1

Returns: 7206144183
94442

63957

7

4

Returns: 6040226994
38766

91558

3

5

Returns: 1774668714
28264

42971

5

8

Returns: 1214532344
24221

34407

6

8

Returns: 208357644
97783

73164

2

7

Returns: 7154195412
54468

5851

4

2

Returns: 79686684
30255

83768

1

6

Returns: 2534400840
72714

8620

7

4

Returns: 626794680
27531

89874

3

5

Returns: 1237160547
17237

43764

6

4

Returns: 188600958
29021

89225

3

10

Returns: 2589398725
43876

86410

1

2

Returns: 3791325160
82682

98974

10

5

Returns: 327349915
77188

84672

7

5

Returns: 3267831168
18737

79870

3

9

Returns: 83146752
18705

71091

2

7

Returns: 1329757155
10832

71178

3

1

Returns: 385500048
60249

33717

5

4

Returns: 2031415533
84000

60880

10

3

Returns: 5113920000
64006

67660

10

1

Returns: 4330645960
9129

10632

7

3

Returns: 48529764
87153

72017

2

4

Returns: 1569164193
76170

80371

2

1

Returns: 6121859070
75427

23697

5

9

Returns: 893696810
16686

92470

1

2

Returns: 1542954420
62380

29759

1

4

Returns: 1856366420
53904

15091

9

7

Returns: 406732632
10397

57611

6

3

Returns: 66561064
43386

46679

6

5

Returns: 2025215094
20096

11054

9

4

Returns: 222141184
23709

9234

9

5

Returns: 109464453
12282

61642

3

10

Returns: 757087044
12

14

6

4

Returns: 42
15

13

6

3

Returns: 25
15

8

4

2

Returns: 32
8

13

4

3

Returns: 104
11

9

1

4

Returns: 99
4

5

2

1

Returns: 20
11

12

1

2

Returns: 132
15

9

1

2

Returns: 135
14

14

3

2

Returns: 196
15

11

1

2

Returns: 165
6

14

2

3

Returns: 84
12

13

1

4

Returns: 156
10

12

3

1

Returns: 60
14

9

1

2

Returns: 126
9

13

1

2

Returns: 117
11

12

4

3

Returns: 132
15

10

1

3

Returns: 75
13

13

3

2

Returns: 169
10

11

4

5

Returns: 110
13

8

4

2

Returns: 28
35630

14

8

9

Returns: 213780
41962

9

9

6

Returns: 4663
159

10

8

7

Returns: 478
13

51884

6

7

Returns: 674492
6

32300

9

3

Returns: 3589
69403

11

6

9

Returns: 46270
51634

8

9

6

Returns: 5738
61636

6

7

5

Returns: 8806
55859

14

9

4

Returns: 782026
65540

11

1

7

Returns: 360470
72260

10

3

6

Returns: 96348
28042

12

5

8

Returns: 168252
18614

13

8

6

Returns: 65149
77967

5

10

1

Returns: 19493
8

98015

7

5

Returns: 196030
5

71784

4

6

Returns: 11964
31638

6

5

7

Returns: 4520
14

95762

9

3

Returns: 79803
18

26434

10

4

Returns: 118953
19628

8

5

8

Returns: 2454
99999

100000

2

4

Returns: 2500000000
99223

99000

3

9

Returns: 545737500
100000

100000

5

9

Returns: 5000000000
100000

100000

1

3

Returns: 5000000000
100000

99999

5

7

Returns: 4999950000
10000

10000

4

10

Returns: 25000000
90002

90002

4

8

Returns: 506295001
3

50000

1

3

Returns: 25001
20

100000

3

10

Returns: 2000000
99999

99999

3

4

Returns: 9999800001
9998

9998

1

2

Returns: 99960004
90456

90404

1

2

Returns: 8177584224
99997

89986

9

7

Returns: 4499165021
50121

13425

8

7

Returns: 672874425
10000

10000

5

9

Returns: 50000000

Statistics

Problem Statement for "KnightCircuit"

Problem Statement

Definition

Constraints

Examples