Statistics

Problem Statement for "BearPaints"

Problem Statement

Limak is a little polar bear. Today he found two things in the snow: a bucket of blue paint and a white rectangular grid with W times H square cells.


Limak is going to paint some (possibly even all) cells blue. He wants to do it in such a way that the blue cells will form a completely filled blue rectangle. He has enough paint for M cells. What is the largest possible area of a blue rectangle he can paint?

Definition

Class:
BearPaints
Method:
maxArea
Parameters:
int, int, long
Returns:
long
Method signature:
long maxArea(int W, int H, long M)
(be sure your method is public)

Constraints

  • W and H will be between 1 and 10^6, inclusive.
  • M will be between 1 and 10^12, inclusive.

Examples

  1. 3

    5

    14

    Returns: 12

    Limak has a grid that is W = 3 cells wide and H = 5 cells tall. He doesn't have enough paint to color all 15 cells. He also cannot color just 14 or 13 cells in a way that would produce a blue rectangle. The best he can do is to color four consecutive rows blue. This will produce a blue rectangle. Its area is 12 squares.

  2. 4

    4

    10

    Returns: 9

    Here the best solution is to paint a rectangle of size 3 times 3 blue. (A square is a valid rectangle.)

  3. 1000000

    12345

    1000000000000

    Returns: 12345000000

    Limak has more than enough paint to make whole grid blue.

  4. 1000000

    1000000

    720000000007

    Returns: 720000000000

    Limak's grid is a square with side 10^6. Limak can paint a rectangle of size 800,000 times 900,000.

  5. 1000000

    1000000

    999999999999

    Returns: 999999000000

  6. 1

    1

    1

    Returns: 1

    fake

  7. 1

    1

    1

    Returns: 1

    fake

  8. 10

    4

    39

    Returns: 36

  9. 5

    200

    969

    Returns: 965

  10. 42

    42

    637

    Returns: 630

  11. 50

    40

    1999

    Returns: 1960

  12. 100

    80

    1999

    Returns: 1998

  13. 1000

    1000

    539513

    Returns: 539513

  14. 1234

    5678

    6266105

    Returns: 6266086

  15. 10000

    11000

    17156467

    Returns: 17156466

  16. 60123

    40444

    1718712911

    Returns: 1718712910

  17. 100000

    100000

    5743503921

    Returns: 5743503921

  18. 222222

    333333

    43915046249

    Returns: 43915046245

  19. 333333

    333333

    18663519622

    Returns: 18663519613

  20. 500000

    500000

    181504473609

    Returns: 181504473598

  21. 500000

    333333

    15535507965

    Returns: 15535507965

  22. 900000

    1000000

    104953809401

    Returns: 104953809400

  23. 1000000

    1000000

    946750292918

    Returns: 946750292895

  24. 1000000

    1000000

    918837635615

    Returns: 918837635606

  25. 1000000

    1000000

    999880002374

    Returns: 999880002304

  26. 1000000

    1000000

    88137170681

    Returns: 88137170681

  27. 1000000

    1000000

    995083890056

    Returns: 995083889634

  28. 1000000

    1000000

    999890002999

    Returns: 999890002989

  29. 1000000

    1000000

    535383495209

    Returns: 535383495207

  30. 1000000

    1000000

    999718003751

    Returns: 999718003497

  31. 1000000

    1000000

    999901001637

    Returns: 999901001580

  32. 1000000

    1000000

    687718841125

    Returns: 687718841121

  33. 1000000

    1000000

    999912001310

    Returns: 999912001260

  34. 1000000

    1000000

    999867003365

    Returns: 999867003300

  35. 1000000

    1000000

    813873836291

    Returns: 813873836288

  36. 1000000

    1000000

    999848004550

    Returns: 999848004480

  37. 1000000

    1000000

    999976000127

    Returns: 999976000119

  38. 1000000

    1000000

    666000272771

    Returns: 666000272768

  39. 1000000

    1000000

    999984000059

    Returns: 999984000055

  40. 1000000

    1000000

    999839006479

    Returns: 999839006478

  41. 1000000

    1000000

    599281916516

    Returns: 599281916516

  42. 1000000

    1000000

    999955000265

    Returns: 999955000234

  43. 1000000

    1000000

    999967000241

    Returns: 999967000230

  44. 1000000

    1000000

    296746755641

    Returns: 296746755633

  45. 1000000

    1000000

    999979000019

    Returns: 999979000000

  46. 1000000

    1000000

    999894002759

    Returns: 999894002745

  47. 919951

    938799

    434438968179

    Returns: 434438968174

  48. 854655

    881521

    752219640699

    Returns: 752219640576

  49. 999836

    913434

    913200891094

    Returns: 913200878800

  50. 939712

    825223

    403562436283

    Returns: 403562436280

  51. 833219

    854736

    711580741944

    Returns: 711580740948

  52. 924438

    893788

    826144937079

    Returns: 826144931891

  53. 985181

    844389

    464714217359

    Returns: 464714217352

  54. 899881

    884588

    795766922387

    Returns: 795766914738

  55. 945146

    886920

    838158167395

    Returns: 838158156745

  56. 840760

    981587

    516927949742

    Returns: 516927949739

  57. 974827

    820344

    799597543517

    Returns: 799597539405

  58. 889669

    862740

    767523296249

    Returns: 767523269324

  59. 804784

    874849

    308149391204

    Returns: 308149391204

  60. 899273

    984644

    885409864660

    Returns: 885409859556

  61. 864672

    952231

    823271757989

    Returns: 823271757120

  62. 807132

    802162

    271635585517

    Returns: 271635585516

  63. 929579

    979863

    910833587079

    Returns: 910833536805

  64. 950514

    823809

    782951243899

    Returns: 782951242240

  65. 863621

    955298

    212637057188

    Returns: 212637057182

  66. 974378

    863991

    841834906175

    Returns: 841834887048

  67. 858201

    824681

    707648289708

    Returns: 707648276398

  68. 969057

    962062

    682267479195

    Returns: 682267479192

  69. 976848

    962657

    940369565135

    Returns: 940368602479

  70. 942463

    982018

    925468500926

    Returns: 925468493470

  71. 999999

    857425

    768971740310

    Returns: 768971740302

  72. 999999

    999999

    999998000000

    Returns: 999997000002

  73. 100000

    100000

    1000000000

    Returns: 1000000000

  74. 999999

    999999

    999986000014

    Returns: 999986000013

  75. 1000000

    1000000

    1000000000000

    Returns: 1000000000000

  76. 1000000

    1000000

    10000000000

    Returns: 10000000000

  77. 12345

    1000000

    1000000000000

    Returns: 12345000000

  78. 99999

    99999

    999999999

    Returns: 999999990

  79. 1000000

    1000000

    10000

    Returns: 10000

  80. 100000

    100000

    1

    Returns: 1

  81. 1000000

    1000000

    1000007

    Returns: 1000007

  82. 3

    3

    10

    Returns: 9

  83. 1000000

    1000000

    3

    Returns: 3

  84. 4

    3

    8

    Returns: 8

  85. 1

    10

    7

    Returns: 7

  86. 4

    4

    16

    Returns: 16

  87. 10

    10

    14

    Returns: 14

  88. 99678

    93467

    1999444332

    Returns: 1999444330

  89. 7

    7

    10

    Returns: 10

  90. 1

    1000000

    1

    Returns: 1

  91. 4

    5

    10

    Returns: 10

  92. 4

    6

    15

    Returns: 15

  93. 1000000

    1000000

    1

    Returns: 1

  94. 30

    30

    97

    Returns: 96

  95. 100000

    100000

    10000000

    Returns: 10000000

  96. 7

    4

    10

    Returns: 10

  97. 11

    4

    11

    Returns: 11

  98. 121212

    545445

    12131346436

    Returns: 12131346436

  99. 1

    1

    2

    Returns: 1

  100. 2

    4

    3

    Returns: 3

  101. 1000000

    1000000

    999999999998

    Returns: 999999000000

  102. 1

    1

    5

    Returns: 1

  103. 6

    3

    18

    Returns: 18

  104. 3

    5

    2

    Returns: 2

  105. 1000000

    999999

    10000000000

    Returns: 10000000000

  106. 3

    4

    1

    Returns: 1

  107. 5

    10

    4

    Returns: 4

  108. 1

    1000000

    9

    Returns: 9

  109. 3

    3

    4

    Returns: 4

  110. 1000000

    1000000

    10

    Returns: 10

  111. 5

    5

    2

    Returns: 2

  112. 100

    100

    50

    Returns: 50

  113. 7

    10

    42

    Returns: 42

  114. 1000000

    1000000

    1000

    Returns: 1000

  115. 1000000

    1000000

    1000000

    Returns: 1000000

  116. 30

    10

    24

    Returns: 24

  117. 5

    7

    22

    Returns: 21

  118. 6

    5

    24

    Returns: 24

  119. 3

    4

    10

    Returns: 9

  120. 121212

    545445

    22000000000

    Returns: 22000000000

  121. 3

    4

    8

    Returns: 8

  122. 5

    4

    6

    Returns: 6

  123. 100000

    3

    34

    Returns: 34

  124. 1

    1

    10

    Returns: 1

  125. 2

    1

    5

    Returns: 2

  126. 5

    3

    10

    Returns: 10

  127. 7

    4

    21

    Returns: 21

  128. 5

    2

    5

    Returns: 5

  129. 5

    10

    50

    Returns: 50

  130. 1000000

    1000000

    851127775848

    Returns: 851127775846

  131. 3

    5

    8

    Returns: 8

  132. 1

    1

    1000000000

    Returns: 1

  133. 10

    10

    73

    Returns: 72

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: