Statistics

Problem Statement for "RochesterSequence"

Problem Statement

This problem has a nonstandard time limit: 4 seconds.

In a Rochester draft there are x people (numbered from 0 to x-1) and 2*x objects of different value. The purpose of the draft is that each person should acquire two of the objects. The draft works as follows:

  1. Going from 0 to x-1, each person picks one of the objects that haven't been picked so far.
  2. Going back from x-1 to 0, each person picks another object. (The very last pick is forced, as there is only one object left.)

A Rochester sequence is a sequence of length 2*x that represents the values of objects in the order in which they have been picked. A Rochester sequence is called nondecreasing ("NRS" for short) if the total values acquired by the people form a nondecreasing sequence. For example, {10, 5, 9, 9, 12, 7} is a NRS because 10+7 <= 5+12 <= 9+9.

You are given a sequence S. You want to erase some (possibly none) elements of S in such a way that what remains will be a NRS. Let L be the largest possible length of that NRS. Let W be the number of ways in which you can erase some elements and obtain a NRS of length L. Return a int[] with two elements: { L, W modulo (10^9 + 7) }.

The sequence S is given in the following format: You are given the int[] Sprefix and the ints n, a, b, and m. Use the following pseudocode to generate S: 

for i = 0 to length(Sprefix)-1:
    S[i] = Sprefix[i]
for i = length(Sprefix) to n-1:
    S[i] = ( S[i-1] * a + b ) modulo m

Definition

Class:
RochesterSequence
Method:
solve
Parameters:
int[], int, int, int, int
Returns:
int[]
Method signature:
int[] solve(int[] Sprefix, int n, int a, int b, int m)
(be sure your method is public)

Notes

  • The reference solution does not depend on any properties of the pseudorandom generator.

Constraints

  • n will be between 2 and 1000, inclusive.
  • Sprefix will contain between 1 and n elements, inclusive.
  • Sprefix will contain at most 200 elements.
  • Each element of Sprefix will be between 0 and 10^9 + 6, inclusive.
  • m will be between 1 and 10^9 + 7, inclusive.
  • Each of a and b will be between 0 and m-1, inclusive.

Examples

  1. {10, 5, 9, 9, 12, 7}

    6

    0

    0

    1

    Returns: {6, 1 }

    The example from the problem statement. As this is a NRS, the only optimal solution is to erase nothing and obtain a NRS of length 6.

  2. {10, 20, 30, 40, 50, 60, 70}

    7

    0

    0

    474747

    Returns: {6, 5 }

    There are five valid ways to erase a single element and obtain a NRS of length 6. Note that the following are not NRSs: {10, 20, 30, 40, 50, 70} {10, 20, 30, 40, 60, 70}

  3. {64, 32, 16, 8, 4, 2, 1}

    7

    0

    0

    1

    Returns: {2, 21 }

    Here the optimal solution is to erase any five of these seven elements. There are 21 ways to do so.

  4. {0}

    1000

    0

    0

    1

    Returns: {1000, 1 }

  5. {47}

    1000

    3156353

    3232535

    1000000007

    Returns: {256, 706709384 }

  6. {1}

    10

    1000

    1

    1000000007

    Returns: {8, 10 }

    Watch out for integer overflow when generating the sequence S. This sequence S looks as follows: 1 1001 1001001 1000994 993994 993994001 993994050 994043050 43043043 43042700.

  7. {1}

    1000

    500000004

    1

    1000

    Returns: {314, 479355352 }

  8. {1}

    1000

    500000004

    0

    1000000007

    Returns: {252, 312692025 }

  9. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    200

    0

    0

    1

    Returns: {98, 144 }

  10. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    200

    0

    0

    1

    Returns: {98, 144 }

  11. {0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801,10000,10201,10404,10609,10816,11025,11236,11449,11664,11881,12100,12321,12544,12769,12996,13225,13456,13689,13924,14161,14400,14641,14884,15129,15376,15625,15876,16129,16384,16641,16900,17161,17424,17689,17956,18225,18496,18769,19044,19321,19600,19881,20164,20449,20736,21025,21316,21609,21904,22201,22500,22801,23104,23409,23716,24025,24336,24649,24964,25281,25600,25921,26244,26569,26896,27225,27556,27889,28224,28561,28900,29241,29584,29929,30276,30625,30976,31329,31684,32041,32400,32761,33124,33489,33856,34225,34596,34969,35344,35721,36100,36481,36864,37249,37636,38025,38416,38809,39204,39601}

    200

    0

    0

    1

    Returns: {98, 87 }

  12. {39601,39204,38809,38416,38025,37636,37249,36864,36481,36100,35721,35344,34969,34596,34225,33856,33489,33124,32761,32400,32041,31684,31329,30976,30625,30276,29929,29584,29241,28900,28561,28224,27889,27556,27225,26896,26569,26244,25921,25600,25281,24964,24649,24336,24025,23716,23409,23104,22801,22500,22201,21904,21609,21316,21025,20736,20449,20164,19881,19600,19321,19044,18769,18496,18225,17956,17689,17424,17161,16900,16641,16384,16129,15876,15625,15376,15129,14884,14641,14400,14161,13924,13689,13456,13225,12996,12769,12544,12321,12100,11881,11664,11449,11236,11025,10816,10609,10404,10201,10000,9801,9604,9409,9216,9025,8836,8649,8464,8281,8100,7921,7744,7569,7396,7225,7056,6889,6724,6561,6400,6241,6084,5929,5776,5625,5476,5329,5184,5041,4900,4761,4624,4489,4356,4225,4096,3969,3844,3721,3600,3481,3364,3249,3136,3025,2916,2809,2704,2601,2500,2401,2304,2209,2116,2025,1936,1849,1764,1681,1600,1521,1444,1369,1296,1225,1156,1089,1024,961,900,841,784,729,676,625,576,529,484,441,400,361,324,289,256,225,196,169,144,121,100,81,64,49,36,25,16,9,4,1,0}

    200

    0

    0

    1

    Returns: {98, 87 }

  13. {0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801,9801,9604,9409,9216,9025,8836,8649,8464,8281,8100,7921,7744,7569,7396,7225,7056,6889,6724,6561,6400,6241,6084,5929,5776,5625,5476,5329,5184,5041,4900,4761,4624,4489,4356,4225,4096,3969,3844,3721,3600,3481,3364,3249,3136,3025,2916,2809,2704,2601,2500,2401,2304,2209,2116,2025,1936,1849,1764,1681,1600,1521,1444,1369,1296,1225,1156,1089,1024,961,900,841,784,729,676,625,576,529,484,441,400,361,324,289,256,225,196,169,144,121,100,81,64,49,36,25,16,9,4,1,0}

    200

    0

    0

    1

    Returns: {200, 1 }

  14. {9801,9604,9409,9216,9025,8836,8649,8464,8281,8100,7921,7744,7569,7396,7225,7056,6889,6724,6561,6400,6241,6084,5929,5776,5625,5476,5329,5184,5041,4900,4761,4624,4489,4356,4225,4096,3969,3844,3721,3600,3481,3364,3249,3136,3025,2916,2809,2704,2601,2500,2401,2304,2209,2116,2025,1936,1849,1764,1681,1600,1521,1444,1369,1296,1225,1156,1089,1024,961,900,841,784,729,676,625,576,529,484,441,400,361,324,289,256,225,196,169,144,121,100,81,64,49,36,25,16,9,4,1,0,0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,1024,1089,1156,1225,1296,1369,1444,1521,1600,1681,1764,1849,1936,2025,2116,2209,2304,2401,2500,2601,2704,2809,2916,3025,3136,3249,3364,3481,3600,3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,5041,5184,5329,5476,5625,5776,5929,6084,6241,6400,6561,6724,6889,7056,7225,7396,7569,7744,7921,8100,8281,8464,8649,8836,9025,9216,9409,9604,9801}

    200

    0

    0

    1

    Returns: {48, 27788 }

  15. {14,0,0,0,1,1,47,0}

    1000

    1

    1

    2

    Returns: {996, 15 }

  16. {47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47}

    1000

    33567948

    230954481

    377792041

    Returns: {216, 678209161 }

  17. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    1000

    33567948

    230954481

    377792041

    Returns: {216, 673244524 }

  18. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    1000

    33567948

    230954481

    377792041

    Returns: {218, 324979798 }

  19. {47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47}

    1000

    487125379

    368797829

    594466507

    Returns: {224, 802186594 }

  20. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    1000

    487125379

    368797829

    594466507

    Returns: {222, 830346031 }

  21. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    1000

    487125379

    368797829

    594466507

    Returns: {222, 223695397 }

  22. {47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47}

    1000

    275116474

    207531246

    276411074

    Returns: {214, 195025977 }

  23. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    1000

    275116474

    207531246

    276411074

    Returns: {214, 145023636 }

  24. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    1000

    275116474

    207531246

    276411074

    Returns: {224, 767830054 }

  25. {47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47}

    1000

    330476968

    21962700

    421352828

    Returns: {214, 451957579 }

  26. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    1000

    330476968

    21962700

    421352828

    Returns: {214, 969941547 }

  27. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    1000

    330476968

    21962700

    421352828

    Returns: {214, 9702411 }

  28. {47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47,47}

    1000

    449395963

    707195153

    853713570

    Returns: {224, 661559320 }

  29. {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050,5151,5253,5356,5460,5565,5671,5778,5886,5995,6105,6216,6328,6441,6555,6670,6786,6903,7021,7140,7260,7381,7503,7626,7750,7875,8001,8128,8256,8385,8515,8646,8778,8911,9045,9180,9316,9453,9591,9730,9870,10011,10153,10296,10440,10585,10731,10878,11026,11175,11325,11476,11628,11781,11935,12090,12246,12403,12561,12720,12880,13041,13203,13366,13530,13695,13861,14028,14196,14365,14535,14706,14878,15051,15225,15400,15576,15753,15931,16110,16290,16471,16653,16836,17020,17205,17391,17578,17766,17955,18145,18336,18528,18721,18915,19110,19306,19503,19701,19900}

    1000

    449395963

    707195153

    853713570

    Returns: {222, 179435025 }

  30. {19900,19701,19503,19306,19110,18915,18721,18528,18336,18145,17955,17766,17578,17391,17205,17020,16836,16653,16471,16290,16110,15931,15753,15576,15400,15225,15051,14878,14706,14535,14365,14196,14028,13861,13695,13530,13366,13203,13041,12880,12720,12561,12403,12246,12090,11935,11781,11628,11476,11325,11175,11026,10878,10731,10585,10440,10296,10153,10011,9870,9730,9591,9453,9316,9180,9045,8911,8778,8646,8515,8385,8256,8128,8001,7875,7750,7626,7503,7381,7260,7140,7021,6903,6786,6670,6555,6441,6328,6216,6105,5995,5886,5778,5671,5565,5460,5356,5253,5151,5050,4950,4851,4753,4656,4560,4465,4371,4278,4186,4095,4005,3916,3828,3741,3655,3570,3486,3403,3321,3240,3160,3081,3003,2926,2850,2775,2701,2628,2556,2485,2415,2346,2278,2211,2145,2080,2016,1953,1891,1830,1770,1711,1653,1596,1540,1485,1431,1378,1326,1275,1225,1176,1128,1081,1035,990,946,903,861,820,780,741,703,666,630,595,561,528,496,465,435,406,378,351,325,300,276,253,231,210,190,171,153,136,120,105,91,78,66,55,45,36,28,21,15,10,6,3,1,0}

    1000

    449395963

    707195153

    853713570

    Returns: {214, 482085339 }

  31. {110011131}

    1000

    21022

    8851881

    25404581

    Returns: {250, 63103846 }

  32. {517063356}

    1000

    777236130

    587001530

    850666236

    Returns: {244, 742355089 }

  33. {985054800}

    1000

    5294512

    9522214

    9809443

    Returns: {252, 837759230 }

  34. {247011036}

    1000

    127636678

    280928225

    459238763

    Returns: {250, 830269440 }

  35. {385561480}

    1000

    474831180

    259897950

    551852548

    Returns: {248, 713057771 }

  36. {602310784}

    1000

    25109937

    23719800

    35717066

    Returns: {250, 729743477 }

  37. {367127108}

    1000

    598922922

    617512215

    645292644

    Returns: {252, 941169089 }

  38. {210435486}

    1000

    256215401

    782917677

    818082096

    Returns: {252, 241502124 }

  39. {37880462}

    1000

    134754154

    358552528

    982424201

    Returns: {254, 674505321 }

  40. {389595010}

    1000

    77625098

    51483060

    105169865

    Returns: {248, 756146615 }

  41. {1 }

    1000

    1000

    1

    1000000007

    Returns: {244, 803138673 }

  42. {1 }

    1000

    1

    1

    10000000

    Returns: {1000, 1 }

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: