Statistics

Problem Statement for "RabbitIncreasing"

Problem Statement

Rabbits often feel lonely, even though they breed a lot.

A male rabbit and a female rabbit were born in July (the 7th month) of year 1, in a certain country. They were the only rabbits in the entire country, so they became a couple.

In March (the 3rd month) of every year, each couple who is strictly more than 1 year old will breed one male and one female rabbit. That is, couples born in year y will start breeding in the year y + 2.

Then, in April (the 4th month) of every year, all newly born rabbits will form couples among themselves. Each rabbit will be a member of exactly one couple, and each couple will contain one male and one female rabbit.

You are given a int[] leaving. Each element of leaving is a year in which half of all couples will leave the country in November (the 11th month). If there are an odd number of couples, n, then (n + 1) / 2 couples will leave. Older couples always have priority when leaving. This means that every couple who leaves will have an age greater than or equal to every couple who stays.

How many couples are in this country in December (the 12th month) of year k? Return the answer modulo 1,000,000,009.

Definition

Class:
RabbitIncreasing
Method:
getNumber
Parameters:
int[], int
Returns:
int
Method signature:
int getNumber(int[] leaving, int k)
(be sure your method is public)

Constraints

  • leaving will contain between 1 and 50 elements, inclusive.
  • k will be between 1 and 10,000,000, inclusive.
  • Each element of leaving will be between 1 and k, inclusive.
  • Elements of leaving will be sorted in strictly increasing order.

Examples

  1. { 3 }

    3

    Returns: 1

    The first couple will breed a pair of rabbits in March of year 3. Since there are 2 couples in November, 1 old pair will leave.

  2. { 5, 9 }

    10

    Returns: 6

    In November of year 5, 3 out of 5 couples will leave. In November of year 9, 5 out of 10 couples will leave.

  3. { 5, 10, 15 }

    19

    Returns: 212

  4. { 2 }

    10000000

    Returns: 0

  5. { 195, 211, 227, 230, 260, 297, 346, 350, 403, 411, 428, 485, 594, 606, 876 }

    1000

    Returns: 975206486

    There are a lot of rabbits. Be sure to return the answer modulo 1,000,000,009.

  6. { 1 }

    1

    Returns: 0

  7. { 1 }

    2

    Returns: 0

  8. { 2 }

    2

    Returns: 0

  9. { 1, 2 }

    2

    Returns: 0

  10. { 1 }

    3

    Returns: 0

  11. { 2 }

    3

    Returns: 0

  12. { 1, 2 }

    3

    Returns: 0

  13. { 3 }

    3

    Returns: 1

  14. { 1, 3 }

    3

    Returns: 0

  15. { 2, 3 }

    3

    Returns: 0

  16. { 1, 2, 3 }

    3

    Returns: 0

  17. { 1 }

    4

    Returns: 0

  18. { 2 }

    4

    Returns: 0

  19. { 1, 2 }

    4

    Returns: 0

  20. { 3 }

    4

    Returns: 1

  21. { 1, 3 }

    4

    Returns: 0

  22. { 2, 3 }

    4

    Returns: 0

  23. { 1, 2, 3 }

    4

    Returns: 0

  24. { 4 }

    4

    Returns: 1

  25. { 1, 4 }

    4

    Returns: 0

  26. { 2, 4 }

    4

    Returns: 0

  27. { 1, 2, 4 }

    4

    Returns: 0

  28. { 3, 4 }

    4

    Returns: 0

  29. { 1, 3, 4 }

    4

    Returns: 0

  30. { 2, 3, 4 }

    4

    Returns: 0

  31. { 1, 2, 3, 4 }

    4

    Returns: 0

  32. { 3 }

    5

    Returns: 2

  33. { 4 }

    5

    Returns: 1

  34. { 5 }

    5

    Returns: 2

  35. { 3, 5 }

    5

    Returns: 1

  36. { 3 }

    6

    Returns: 3

  37. { 4 }

    6

    Returns: 2

  38. { 5 }

    6

    Returns: 2

  39. { 3, 5 }

    6

    Returns: 1

  40. { 6 }

    6

    Returns: 4

  41. { 3, 6 }

    6

    Returns: 1

  42. { 4, 6 }

    6

    Returns: 1

  43. { 5, 6 }

    6

    Returns: 1

  44. { 3 }

    7

    Returns: 5

  45. { 4 }

    7

    Returns: 3

  46. { 5 }

    7

    Returns: 4

  47. { 3, 5 }

    7

    Returns: 2

  48. { 6 }

    7

    Returns: 5

  49. { 3, 6 }

    7

    Returns: 1

  50. { 4, 6 }

    7

    Returns: 1

  51. { 5, 6 }

    7

    Returns: 2

  52. { 7 }

    7

    Returns: 6

  53. { 3, 7 }

    7

    Returns: 2

  54. { 4, 7 }

    7

    Returns: 1

  55. { 5, 7 }

    7

    Returns: 2

  56. { 3, 5, 7 }

    7

    Returns: 1

  57. { 6, 7 }

    7

    Returns: 2

  58. { 5, 6, 7 }

    7

    Returns: 1

  59. { 9999951, 9999952, 9999953, 9999954, 9999955, 9999956, 9999957, 9999958, 9999959, 9999960, 9999961, 9999962, 9999963, 9999964, 9999965, 9999966, 9999967, 9999968, 9999969, 9999970, 9999971, 9999972, 9999973, 9999974, 9999975, 9999976, 9999977, 9999978, 9999979, 9999980, 9999981, 9999982, 9999983, 9999984, 9999985, 9999986, 9999987, 9999988, 9999989, 9999990, 9999991, 9999992, 9999993, 9999994, 9999995, 9999996, 9999997, 9999998, 9999999, 10000000 }

    10000000

    Returns: 668858438

  60. { 9999902, 9999904, 9999906, 9999908, 9999910, 9999912, 9999914, 9999916, 9999918, 9999920, 9999922, 9999924, 9999926, 9999928, 9999930, 9999932, 9999934, 9999936, 9999938, 9999940, 9999942, 9999944, 9999946, 9999948, 9999950, 9999952, 9999954, 9999956, 9999958, 9999960, 9999962, 9999964, 9999966, 9999968, 9999970, 9999972, 9999974, 9999976, 9999978, 9999980, 9999982, 9999984, 9999986, 9999988, 9999990, 9999992, 9999994, 9999996, 9999998, 10000000 }

    10000000

    Returns: 503948594

  61. { 9999853, 9999856, 9999859, 9999862, 9999865, 9999868, 9999871, 9999874, 9999877, 9999880, 9999883, 9999886, 9999889, 9999892, 9999895, 9999898, 9999901, 9999904, 9999907, 9999910, 9999913, 9999916, 9999919, 9999922, 9999925, 9999928, 9999931, 9999934, 9999937, 9999940, 9999943, 9999946, 9999949, 9999952, 9999955, 9999958, 9999961, 9999964, 9999967, 9999970, 9999973, 9999976, 9999979, 9999982, 9999985, 9999988, 9999991, 9999994, 9999997, 10000000 }

    10000000

    Returns: 225971647

  62. { 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 }

    10000000

    Returns: 0

  63. { 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99 }

    10000000

    Returns: 88081120

  64. { 20448, 20630, 20837, 23680, 23693, 24776, 28012, 46910, 57846, 58401, 62165, 63805, 70773, 73010, 75318, 79020, 80906, 84943, 85644, 87335, 100531, 104499, 107794, 109060, 114830, 115385, 122281, 130059, 131108, 134086, 134667, 139723, 154473, 156163, 156347, 165847, 173145, 174075, 180535, 193840, 199052, 203624, 206070, 222676, 222706, 225213, 234614, 240932 }

    242811

    Returns: 16770971

  65. { 42, 225, 252, 279, 337, 375 }

    446

    Returns: 186816480

  66. { 1377, 3234, 3518, 4831, 5038, 5039, 5811, 6429, 8037, 8909, 8989, 11429, 11957, 19078, 19190, 19862, 21733, 22513, 22575, 22703, 24399, 26162, 30057, 31074, 31468, 31623, 31968, 32579, 33427, 39232, 39344, 39834, 40001, 40503, 45791, 47479, 52149 }

    54977

    Returns: 949797228

  67. { 53, 70, 76, 165, 211, 214, 282, 294, 352, 364, 427, 454, 492, 518, 562, 610, 683, 714, 721, 739, 769, 801, 880, 885, 903, 928, 1126, 1210, 1211, 1257, 1277, 1282, 1368, 1413, 1457, 1459, 1588, 1589, 1625, 1628, 1641, 1649, 1661, 1696, 1762 }

    1769

    Returns: 262048960

  68. { 1, 8, 22, 23, 34, 45, 47, 55, 61, 64, 65, 72, 73, 74, 78, 85, 86, 87, 88, 89, 90, 93, 97, 102, 104, 116, 124, 138, 139, 144, 147, 149, 155, 163, 169, 174, 176, 183, 188, 192, 201, 202, 203, 213, 223 }

    223

    Returns: 0

  69. { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 21, 25, 27 }

    27

    Returns: 0

  70. { 1, 159, 215, 325, 431, 475, 477, 603, 626, 705, 785, 857, 876, 1008, 1208, 1501, 1636, 1772, 1795, 1797 }

    1798

    Returns: 0

  71. { 202201, 343595, 346910, 688073, 785690, 975844, 1053041, 1094677, 1153147, 1548258, 1583178, 1621426, 1656316, 1678333, 1755216, 2108301, 2126603, 2360447, 2429492, 2470241, 2484986, 2551174, 2694964, 2735632, 2812277, 2920386, 2963195, 3270604, 3386928, 3469029, 3919261, 3971151, 4050684, 4776787, 4834524, 4870395, 4937867, 5061655, 5085142, 5189760, 5645238, 5788290, 5973553, 6036739, 6230379, 6300201, 6328506, 6383279, 6406882 }

    6425044

    Returns: 6134042

  72. { 42, 99, 141, 163, 194, 250, 255, 261, 271, 291, 350, 386, 426, 428, 592, 650, 784, 862, 890, 969, 970, 975, 1037, 1068, 1072, 1180, 1239, 1248, 1257, 1258, 1276, 1348, 1362, 1398, 1403, 1416, 1439, 1578, 1585, 1635 }

    1647

    Returns: 952607219

  73. { 386, 2111, 3559, 5663, 6608, 7294 }

    7448

    Returns: 718345633

  74. { 830722, 1519602, 1590816, 1924726, 2159961, 2470442, 2504960, 2647336, 3082631, 4262616, 4370676, 4553976, 4564380 }

    4865046

    Returns: 106491565

  75. { 170, 4362, 11111, 28355, 34122, 41044, 44945, 54811, 58615, 58917, 72782, 76700, 88390, 89632, 109228, 110362, 128793, 136369, 150764, 163945, 173263, 175128, 186390, 202581, 218699, 224581, 247920, 256528, 265576, 278130, 278438, 291970, 292107 }

    312062

    Returns: 473474015

  76. { 31, 34, 53, 77, 100, 102, 119, 142, 158, 160, 183, 211, 234, 235, 272, 285, 312, 344, 358, 381, 399, 418, 427, 471, 501, 534, 624, 686, 697, 708, 726, 827, 878, 880, 953, 1004, 1015 }

    1024

    Returns: 31095667

  77. { 58, 186, 191, 232, 481, 502, 643, 718, 728, 748, 857, 1150, 1166, 1177, 1201, 1268, 1300, 1327, 1332, 1356, 1454, 1470, 1567, 1626, 1670, 1733, 1771, 1829, 1879, 1891, 2009, 2013, 2039, 2157, 2279 }

    2334

    Returns: 265986389

  78. { 2, 18, 25, 29, 30, 41, 42, 46, 47, 50, 51, 53, 54, 56, 57, 60, 61, 63, 64, 66, 67, 70, 72, 75, 79, 82, 84, 86, 88, 103, 109, 110, 115, 117, 118, 119, 120, 121, 132, 133, 134 }

    135

    Returns: 0

  79. { 31, 48, 59, 61, 75, 89, 119, 164, 169, 230, 372, 452, 471, 472, 548, 657, 683, 701, 806, 836, 838, 853, 866, 894, 899, 951, 1016, 1077, 1082, 1083, 1092, 1148, 1153, 1193, 1243, 1320, 1323, 1366, 1433 }

    1449

    Returns: 240283473

  80. { 28206, 55910, 207475, 220447, 244264, 536331, 679980, 742980, 779437, 784691, 887974, 967072, 1041257, 1073666, 1324454, 1482206, 1573587, 1588027, 1634894, 1753880, 1888638, 1893043, 1923914, 1962835, 2031414, 2237697, 2283338, 2461657 }

    2631605

    Returns: 635495604

  81. { 15725, 16176, 17964, 36965, 38469, 43366, 47213, 48589, 50419, 51913, 57769, 58032, 61836, 71594, 76062, 90228, 100573, 107241, 111338, 114178, 119719, 122552, 127756, 135315, 136478, 140101, 140272, 143192, 157255, 158990, 160551 }

    162504

    Returns: 329864564

  82. { 33518, 46003, 46760, 113099, 217202, 272542, 308708, 321630, 353005, 397480, 476556, 522574, 602807, 603754, 698895, 729752, 859277, 861454, 872062, 894000, 926569, 983949, 1053718, 1053816, 1141346, 1172811, 1212566, 1272861, 1337001, 1342854, 1487226, 1500640, 1631587, 1652884, 1768573, 1788821, 1810498, 1835934, 1848605, 1872304, 1924947, 2055783, 2067767, 2067968, 2090147, 2153425, 2208500, 2274339 }

    2287861

    Returns: 868680112

  83. { 29836, 31467, 108722, 124525, 124963, 133956, 168840, 196449 }

    200872

    Returns: 568322828

  84. { 12409, 16582, 20385, 40500 }

    41567

    Returns: 291906104

  85. { 11, 41, 51, 80, 99, 177, 184, 247, 258, 263, 285, 310, 337, 573, 650, 723, 774, 788, 798, 864, 880, 967, 1063, 1077, 1078, 1114, 1117 }

    1194

    Returns: 245832349

  86. { 113772, 345565, 563525, 566755, 640193, 686756, 727397, 739258, 763723, 806966, 822400 }

    854794

    Returns: 566456916

  87. { 52, 242, 288, 327, 603, 945, 1025, 1046, 1264, 1353, 1450, 1629, 1880, 1947, 2009, 2293, 2386, 2574, 2729, 2906, 2918, 3106, 3330, 3385, 3658, 3793 }

    4025

    Returns: 310606505

  88. { 13, 1225, 1283, 1336, 1865, 4007, 4056, 4830, 5185, 5318, 5650, 5685, 5988, 6002, 6741, 6884, 7748, 8313, 8330, 8853, 8948, 9243, 9376, 10174, 10348, 11419, 11467, 12125, 12191, 12337, 12384, 13339, 13779, 13863, 14663 }

    15057

    Returns: 203474244

  89. { 155, 1266, 1841, 1900, 2536, 2623, 4604, 5389, 6639, 6852, 7644, 8081, 8099, 8416, 8932 }

    10068

    Returns: 311432888

  90. { 54, 2141, 4267, 4899, 5450, 5501, 5769 }

    6797

    Returns: 104195643

  91. { 456, 3875, 5991, 6077, 8901, 11202, 11217, 12579, 24076, 25939, 37309, 42946, 45396, 46172, 47684, 51265, 52745, 53588, 53769, 54810, 55092, 57476 }

    59427

    Returns: 812752270

  92. { 42724, 79166, 188247, 434407, 480631, 564878, 650656, 652493, 708988, 931761, 946156, 1115360, 1133583, 1175049, 1483982, 1580690, 1661151, 1728254, 1879486, 1898767, 1953963, 2050474, 2055567, 2080250 }

    2497937

    Returns: 348111187

  93. { 1, 135, 148, 157, 197, 218, 294, 336, 342, 347, 350, 351, 352, 354, 361, 370, 383, 393, 406, 418, 463, 495, 499, 569, 586, 656, 766, 793, 794, 821, 978, 989, 1018, 1101, 1148, 1156, 1234, 1375, 1457 }

    1464

    Returns: 0

  94. { 8, 21, 31, 38, 74, 148, 157, 184, 186, 197, 205, 210, 318, 320, 331, 334, 348, 512 }

    523

    Returns: 710291366

  95. { 6432, 9177, 42539, 53265, 61371, 95617, 108401, 113986, 115568, 117994, 124219, 139506, 145072, 151245, 151348, 156317, 197301, 200664, 231375, 237006, 246838, 261941, 273893, 285809, 288631, 292995, 298114, 298297, 303202, 367460, 374811, 375703, 383460, 384923, 391483, 393260, 423760, 465817, 469516, 514519, 533822, 544412 }

    545082

    Returns: 826244726

  96. { 129, 570, 795, 907, 1270, 1340, 1455, 1547, 1653, 1736, 1787, 1804, 1825, 1923, 2039, 2153, 2478, 2484, 2821, 3001, 3079, 3207, 3226, 3334, 3566, 3602, 3616, 3700, 3707, 4058, 4358, 4743, 4787, 4860, 5339, 5762, 5847, 5866, 6305, 6415, 6448, 6467, 6528, 6539 }

    6585

    Returns: 81373743

  97. { 409, 675, 699, 709, 749, 833, 857, 922, 1040, 1224, 1242, 1252, 1641, 1762, 1765, 1778, 1876 }

    1880

    Returns: 13854960

  98. { 808, 817, 910, 1005 }

    1406

    Returns: 888302

  99. { 12387, 35991, 68999, 115829, 303971, 311351, 344367, 426318, 450781, 475920, 639402, 782087, 829785, 848738, 893159, 1023373, 1118761, 1185102, 1388493, 1452467, 1485695, 1492527, 1536363, 1557876, 1629690, 1642685, 1692899, 1796702, 1861775, 1876618, 1884217, 1917341, 1922179, 1990556, 2053730, 2079399, 2127478, 2146394 }

    2186646

    Returns: 509744526

  100. { 1, 2, 10 }

    11

    Returns: 0

  101. {11111, 11112, 11113, 11114, 11115, 11116, 11117, 11118, 11119, 11120, 11121, 11122, 11123, 11124, 11125, 11126, 11127, 11128, 11129, 11130, 11131, 11132, 11133, 11134, 11135, 11136, 11137, 11138, 11139, 11140, 11141, 11142, 11143, 11144, 11145, 11146, 11147, 11148, 11149, 11150, 11151, 11152, 11153, 11154, 11155, 11156, 11157, 11158, 11159, 11160}

    15000

    Returns: 81622123

  102. {11111, 11112, 11113, 11114, 11115, 11116, 11117, 11118, 11119, 11120, 11121, 11122, 11123, 11124, 11125, 11126, 11127, 11128, 11129, 11130, 11131, 11132, 11133, 11134, 11135, 11136, 11137, 11138, 11139, 11140, 11141, 11142, 11143, 11144, 11145, 11146, 11147, 11148, 11149, 11150, 11151, 11152, 11153, 11154, 11155, 11156, 11157, 11158, 11159, 11160}

    11161

    Returns: 916922290

  103. {9111111, 9111112, 9111113, 9111114, 9111115, 9111116, 9111117, 9111118, 9111119, 9111120, 9111121, 9111122, 9111123, 9111124, 9111125, 9111126, 9111127, 9111128, 9111129, 9111130, 9111131, 9111132, 9111133, 9111134, 9111135, 9111136, 9111137, 9111138, 9111139, 9111140, 9111141, 9111142, 9111143, 9111144, 9111145, 9111146, 9111147, 9111148, 9111149, 9111150, 9111151, 9111152, 9111153, 9111154, 9111155, 9111156, 9111157, 9111158, 9111159, 9111160}

    9999999

    Returns: 477491848

  104. {195, 211, 227, 230, 260, 297, 346, 350, 403, 411, 428, 485, 594, 606, 876 }

    1000

    Returns: 975206486

  105. {81843, 203841, 223102, 579549, 707955, 928779, 995896, 1196860, 1330468, 1370300, 2240440, 2334334, 2588146, 2683539, 2714501, 2808465, 3423725, 3744542, 4102869, 4115036, 4325727, 4469437, 4519712, 4864154, 5008828, 5129895, 5216758, 5540665, 5778083, 5818309, 5851943, 6470649, 6526605, 7205539, 7325359, 7490717, 7531645, 8043324, 8140624, 8295806, 8486730, 8519812, 8752492, 8919377, 9145742, 9246107, 9288943, 9356383, 9827913, 9855351 }

    10000000

    Returns: 438814806

  106. {10000000 }

    10000000

    Returns: 236946917

  107. {10000, 10001, 10002, 10003, 10004, 20000, 30000, 40000 }

    10000000

    Returns: 723089896

  108. {100, 200, 201, 300, 3000, 123456, 123458, 999999, 1000100, 2000000, 9999990 }

    9999997

    Returns: 719252766

  109. {7000000, 7000001, 7000002, 7000003, 7000004, 7000005, 7000006, 7000007, 7000008, 7000009, 7000010, 7000011, 7000012, 7000013, 7000014, 7000015, 7000016, 7000017, 7000018, 7000019, 7000020, 7000021, 7000022, 7000023, 7000024, 7000025, 7000026, 7000027, 7000028, 7000029, 7000030, 7000031, 7000032, 7000033, 7000034, 7000035, 7000036, 7000037, 7000038, 7000039, 7000040, 7000041, 7000042, 7000043, 7000044, 7000045, 7000046, 7000047, 7000048, 7000049 }

    10000000

    Returns: 526195138

  110. {10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, 110000, 120000, 130000, 140000, 150000, 160000, 170000, 180000, 190000, 200000, 210000, 220000, 230000, 240000, 250000, 260000, 270000, 280000, 290000, 300000, 310000, 320000, 330000, 340000, 350000, 360000, 370000, 380000, 390000, 400000, 410000, 420000, 430000, 440000, 450000, 460000, 470000, 480000, 490000, 500000 }

    10000000

    Returns: 100088771

  111. {500003, 500004, 500005, 500006, 500007, 500008, 500009, 500010, 9100001, 9100002, 9100003, 9100004, 9100005, 9100006, 9100007, 9100009, 9100010, 9900001, 9900002, 9900003, 9900004, 9900005, 9900006, 9900007, 9900008, 9900009, 9900010 }

    10000000

    Returns: 95730541

  112. {999999 }

    10000000

    Returns: 115550965

  113. {1000000 }

    10000000

    Returns: 795702849

  114. {198, 1588, 2198, 2288, 2635, 3022, 3094, 3196, 3579, 3672, 4600, 5250, 5845, 6039, 6192, 6225, 6557, 6619, 7409, 7449, 7959, 8714, 9057, 9504, 9703, 9923, 10956, 11009, 11512, 12009, 12102, 12293, 13459, 14344, 14799, 14990, 15282, 16203, 16520, 18191, 18539, 19157, 19590, 19797, 19816, 20056, 20329, 20473, 20486, 20581 }

    20601

    Returns: 350354224

  115. {3 }

    1004

    Returns: 102915696

  116. {195, 211, 227, 230, 260, 297, 346, 350, 403, 411, 428, 485, 594, 606, 9899999 }

    10000000

    Returns: 696736572

  117. {1 }

    20

    Returns: 0

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: