Statistics

Problem Statement for "GreedyGrid"

Problem Statement

Fox Jiro and Eel Saburo are good friends. One day Jiro gives Saburo the following problem:


You are given a rectangular grid. It is H cells high and W cells wide. Each cell of the grid contains a non-negative integer which is between 0 and S, inclusive. The top-left cell of the grid always contains 0.


First you are on the top-left cell of the grid. You move in steps. In each step, you can go either down or right to the immediately adjacent cell. Your path terminates when you reach the bottom-right cell of the grid. Let K be the sum of integers contained in the cells which you visited (including the bottom-right cell). What is the maximum possible value of K?


This is a well-known classical problem solvable by dynamic programming. But Saburo doesn't know the clever solution. He found the following greedy approach to this problem:


  • If he is in the rightmost column, he takes a step down. If he is in the bottommost row, he takes a step right.
  • Otherwise, he goes to the cell which contains the bigger integer. If two adjacent cells have same integer, he goes to the right cell.

Jiro is interested in Saburo's greedy approach. He calls a grid p-greedy if the sum of integers visited by the greedy algorithm is equal to p.


You are given the ints H, W, and S. Let X be the number of different S-greedy grids with the given dimensions and values. Return the value (X modulo 10,007).

Definition

Class:
FoxAndGreed
Method:
count
Parameters:
int, int, int
Returns:
int
Method signature:
int count(int H, int W, int S)
(be sure your method is public)

Constraints

  • H will be between 1 and 2500, inclusive.
  • W will be between 1 and 2500, inclusive.
  • S will be between 0 and 100, inclusive.

Examples

  1. 2

    2

    1

    Returns: 4

    These are the 4 grids: 01 01 00 00 00 10 10 01

  2. 2

    2

    2

    Returns: 9

    These are the 9 grids: 02 02 02 01 01 00 00 01 00 00 10 20 01 11 11 20 20 02

  3. 2

    2

    0

    Returns: 1

  4. 47

    58

    100

    Returns: 1301

  5. 1234

    2345

    97

    Returns: 8894

  6. 1

    2500

    100

    Returns: 7254

  7. 1

    2499

    99

    Returns: 3246

  8. 2500

    1

    100

    Returns: 7254

  9. 2499

    1

    99

    Returns: 3246

  10. 1

    1

    0

    Returns: 1

  11. 1

    1

    1

    Returns: 0

  12. 1

    1

    100

    Returns: 0

  13. 1

    1234

    0

    Returns: 1

  14. 1234

    1

    0

    Returns: 1

  15. 13

    25

    0

    Returns: 1

  16. 13

    25

    1

    Returns: 1716

  17. 1134

    2241

    1

    Returns: 1971

  18. 1134

    2241

    0

    Returns: 1

  19. 2429

    2152

    0

    Returns: 1

  20. 3

    3

    0

    Returns: 1

  21. 1611

    2123

    61

    Returns: 2230

  22. 139

    967

    85

    Returns: 7925

  23. 82

    1006

    72

    Returns: 2353

  24. 2420

    1268

    55

    Returns: 7599

  25. 1431

    1961

    93

    Returns: 2064

  26. 2333

    542

    27

    Returns: 3106

  27. 1405

    2023

    40

    Returns: 1981

  28. 1005

    339

    98

    Returns: 8994

  29. 1130

    908

    85

    Returns: 2023

  30. 296

    1669

    74

    Returns: 1225

  31. 872

    519

    36

    Returns: 7051

  32. 2204

    679

    9

    Returns: 6356

  33. 1306

    850

    99

    Returns: 7047

  34. 370

    1860

    83

    Returns: 9749

  35. 588

    2044

    67

    Returns: 1399

  36. 1899

    2143

    75

    Returns: 6103

  37. 770

    862

    35

    Returns: 4226

  38. 70

    1433

    27

    Returns: 1456

  39. 1573

    2084

    77

    Returns: 7863

  40. 273

    587

    78

    Returns: 4121

  41. 960

    600

    83

    Returns: 4280

  42. 2434

    897

    9

    Returns: 9372

  43. 1295

    550

    80

    Returns: 669

  44. 1866

    2148

    32

    Returns: 9241

  45. 999

    678

    76

    Returns: 184

  46. 711

    2345

    68

    Returns: 7021

  47. 608

    1457

    1

    Returns: 7194

  48. 1722

    2007

    100

    Returns: 3537

  49. 1069

    631

    73

    Returns: 2326

  50. 1087

    2344

    65

    Returns: 4769

  51. 103

    1346

    48

    Returns: 6147

  52. 219

    1994

    93

    Returns: 4801

  53. 1577

    1928

    99

    Returns: 4212

  54. 961

    332

    65

    Returns: 8791

  55. 2142

    1489

    7

    Returns: 8693

  56. 2022

    1219

    60

    Returns: 2497

  57. 70

    1807

    46

    Returns: 3453

  58. 306

    2171

    15

    Returns: 1365

  59. 2403

    2018

    94

    Returns: 3564

  60. 2300

    1292

    33

    Returns: 2870

  61. 2313

    1447

    22

    Returns: 3093

  62. 1826

    1544

    42

    Returns: 9004

  63. 499

    1350

    17

    Returns: 4815

  64. 1796

    1371

    76

    Returns: 4708

  65. 1130

    298

    21

    Returns: 7046

  66. 826

    184

    56

    Returns: 1726

  67. 749

    373

    73

    Returns: 3760

  68. 892

    776

    18

    Returns: 3928

  69. 1098

    472

    88

    Returns: 8261

  70. 152

    1702

    16

    Returns: 6676

  71. 2500

    2500

    100

    Returns: 6038

  72. 2500

    2500

    90

    Returns: 7464

  73. 2500

    2500

    80

    Returns: 6857

  74. 2500

    2500

    70

    Returns: 2498

  75. 2500

    2500

    60

    Returns: 355

  76. 2500

    2500

    50

    Returns: 9910

  77. 2500

    2500

    40

    Returns: 8090

  78. 2500

    2500

    30

    Returns: 7413

  79. 2500

    2500

    20

    Returns: 358

  80. 2500

    2500

    10

    Returns: 2733

  81. 2500

    2500

    0

    Returns: 1

  82. 2500

    2499

    100

    Returns: 5105

  83. 2499

    2500

    100

    Returns: 7913

  84. 2499

    2499

    99

    Returns: 2045

  85. 2500

    2500

    99

    Returns: 4967

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: