TopCoder Statistics - Problem Statement

Problem Statement

Bob has a width x height rectangular board divided into 1 x 1 cells. Rows of the board are numbered 0 to height-1 and columns are numbered 0 to width-1.

Each cell can contain at most one stone, and the Euclidean distance between each pair of stones must not equal 2. The Euclidean distance between cell in row x1, column y1 and cell in row x2, column y2 is defined as the square root from (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2).

Return the maximal number of stones he can place on the board.

Definition

Class:: NotTwo
Method:: maxStones
Parameters:: int, int
Returns:: int
Method signature:: int maxStones(int width, int height)
(be sure your method is public)

Constraints

width will be between 1 and 1000, inclusive.
height will be between 1 and 1000, inclusive.

Examples

3

2

Returns: 4

He can place four stones on the board. Here is one possible arrangement: - * * * * -
3

3

Returns: 5

* - - * * - - * *
8

5

Returns: 20
1

1

Returns: 1
1

2

Returns: 2
1

3

Returns: 2
1

4

Returns: 2
2

1

Returns: 2
2

2

Returns: 4
2

3

Returns: 4
2

4

Returns: 4
3

1

Returns: 2
3

2

Returns: 4
3

3

Returns: 5
3

4

Returns: 6
4

1

Returns: 2
4

2

Returns: 4
4

3

Returns: 6
4

4

Returns: 8
997

997

Returns: 497005
997

998

Returns: 497504
997

999

Returns: 498002
997

1000

Returns: 498500
998

997

Returns: 497504
998

998

Returns: 498004
998

999

Returns: 498502
998

1000

Returns: 499000
999

997

Returns: 498002
999

998

Returns: 498502
999

999

Returns: 499001
999

1000

Returns: 499500
1000

997

Returns: 498500
1000

998

Returns: 499000
1000

999

Returns: 499500
1000

1000

Returns: 500000
1

934

Returns: 468
744

263

Returns: 97836
530

701

Returns: 185766
509

753

Returns: 191639
257

257

Returns: 33025
120

712

Returns: 42720
352

844

Returns: 148544
706

109

Returns: 38478
394

331

Returns: 65208
367

170

Returns: 31196
933

918

Returns: 428248
848

973

Returns: 412552
869

981

Returns: 426245
224

550

Returns: 61600
593

165

Returns: 48923
170

552

Returns: 46920
428

191

Returns: 40874
625

636

Returns: 198750
921

945

Returns: 435173
311

863

Returns: 134197
1

234

Returns: 118
965

1

Returns: 483
1

534

Returns: 268
621

1

Returns: 311
2

6

Returns: 8
997

883

Returns: 440176
11

6

Returns: 34
992

945

Returns: 468720
6

1

Returns: 4
1

6

Returns: 4
5

6

Returns: 16
7

1

Returns: 4
901

1000

Returns: 450500
236

935

Returns: 110330
10

10

Returns: 52
18

18

Returns: 164
867

461

Returns: 199844
666

667

Returns: 222112
25

25

Returns: 313
2

5

Returns: 6
5

2

Returns: 6
980

817

Returns: 400330
6

6

Returns: 20
234

34

Returns: 3980
6

3

Returns: 10
5

3

Returns: 8
95

74

Returns: 3516
706

146

Returns: 51540
5

5

Returns: 13
999

987

Returns: 493007
49

47

Returns: 1152
6

4

Returns: 12
6

2

Returns: 8
1000

872

Returns: 436000
1

100

Returns: 50
10

11

Returns: 56
10

1

Returns: 6
42

18

Returns: 380
58

214

Returns: 6208
3

6

Returns: 10
1

99

Returns: 50
11

11

Returns: 61
20

5

Returns: 50
777

127

Returns: 49340
955

599

Returns: 286023
1

9

Returns: 5
989

899

Returns: 444556

Statistics

Problem Statement for "NotTwo"

Problem Statement

Definition

Constraints

Examples