TopCoder Statistics - Problem Statement

Problem Statement

A long time ago in a galaxy far, far away the Jedi Academy conducted a test to detect children with high Force sensitivy which would then be trained to become Jedi. The test was conducted in the Jedi Temple which had several floors. You are given a int[] students which has as many elements as there are floors in the building. For each i, students[i] is the number of children on the i-th floor (0-based index).

During the test, the children will be supervised by Yoda and possibly also by some other Jedi. Each Jedi, including Yoda, can only supervise children on one of the floors. Additionally, there is a limit on how many children a single Jedi may supervise: Yoda is able to supervise up to Y children, inclusive, and any other Jedi is able to supervise up to J children, inclusive. Each child has to be supervised by some Jedi.

For example:
Yoda and a single other Jedi can supervise a floor that contains up to Y+J children.
Two Jedi can supervise a floor that contains up to 2J children.

Find the minimum number of Jedi which were required to help Yoda so that every child at each floor was supervised. Note that Yoda may choose which floor he wants to supervise, and that the answer may sometimes be zero.

Definition

Class:: TheJediTestDiv2
Method:: countSupervisors
Parameters:: int[], int, int
Returns:: int
Method signature:: int countSupervisors(int[] students, int Y, int J)
(be sure your method is public)

Constraints

students will contain between 1 and 50 elements, inclusive.
Each element in students will be between 0 and 1000, inclusive.
J will be between 1 and 999, inclusive.
Y will be between J+1 and 1000, inclusive.

Examples

{10, 15}

12

5

Returns: 3

Yoda can supervise at most 12 children, so he can either supervise all kids on floor 0, or 12 out of the 15 children on floor 1. If Yoda supervises floor 0, we need three other Jedi on floor 1. If Yoda supervises a part of floor 1, we need one other Jedi on floor 1 and two more for floor 0. In either case, there have to be at least 3 Jedi other than Yoda.
{11, 13, 15}

9

5

Returns: 7

In the optimal solution, Yoda will supervise either on floor 0 or on floor 1. In either case we need one Jedi to help him on his floor, and three Jedi for each of the other two floors. Note that if Yoda chooses floor 2, eight additional Jedi would be needed.
{10}

100

2

Returns: 0

Yoda can handle the entire floor.
{0, 0, 0, 0, 0}

145

21

Returns: 0

For the Jedi Academy, a bad day it was.
{4, 7, 10, 5, 6, 55, 2}

20

3

Returns: 26
{45,551,575,17,90,488,22,195,278,659,36,251,663,341,129,6,481,398,778,360,297,545,869,798,739,684,711,928,986,85,885,586,723,341,453,552,507,123,648,920,573,956,919,739,963,391,385}

201

194

Returns: 143
{116,689,301,755,311,150,582,835,440,943,708,969,612}

630

294

Returns: 30
{985,37,940,856,793,314,755,558,675,661,953,424,342,190,584,226,244,956,440,681,852,700,944,129,344,944,95}

517

219

Returns: 84
{432,799,320,235,730,242,54,824,734,310,447,496,572,332,862,882,600,435,647,336,358,700,369,230,5,215,981,569,49,939}

134

133

Returns: 125
{94,451,47,285,729,904,829,687,992,902,498,920,590,741,663,159,929,33,50,225,361,265,261}

204

191

Returns: 71
{418,628,404,19,533,600,561,52,893,62,790,50,808,72,741,135,628,300,966,148,983,852,703,312,872,837,659,964,331,314,743,439,115,204,31,418,34,518,616,562,330,788,317}

196

22

Returns: 952
{732,825,749,511,467,306,742,532,934,791,866,972,547,646,529,929,762,461,622,886,891,353,894,902,314,526,939,940,266,238,779,167,94,620,63,385,556,418,523,893,459,644,403,989,704}

66

49

Returns: 589
{572,413,803,177,944,820,689,155,962,177,440,473,545,711,122,764,85,800,800,577,591,849,50,287,517,627,402,685,551,701,366,753,640,333,234,896,627,163,724,347,974,279,73,800,154,834,210,338,517,169}

248

69

Returns: 394
{560,919,798,730,31,834,393,520,430,227,850,37,829,274,335,679,629,872,404,986,210,229,15,585,789,110,622,422}

153

93

Returns: 166
{939,784,554,559,337,905,470,339}

210

98

Returns: 51
{732,242,353,371,686,220,170,671,561,215,298,315,374,451,455,179,933,983,473,687,573,72,960,440}

568

54

Returns: 212
{889,241,942,573,688,274,185,725,628,692,79,508,667,53,71,410,889,19,390,532,972,925,703,240,30,730}

329

225

Returns: 72
{306,959,16,721,161,201,223,436,667,546,909,620,572,379,429,10,66,12,790,30,962,198,901,394,603,827,416,941,995,528}

458

417

Returns: 51
{169,513,153,611,479,360,565,544,303,34,450}

284

70

Returns: 62
{301,929,661,141,972,302,226,248,115,583,17,674,264,559,597,207,885,594}

184

66

Returns: 132
{905,2,4,732,374,534,675,69,434,452,105,680,562,160,971,967,714,16,931,225,593,274,865,696,969,57,253,407,419,239,709,100,757,856}

392

65

Returns: 267
{455,366,840,955,627}

881

160

Returns: 16
{787,167,426,169,199,95,135,239,111}

38

7

Returns: 331
{841,591,619,878,616,149,776,139,999,651,785,973,730,387,343,3,952,262,304,205,811,846,284,916,631,46,742,11,974,445,273,262,113,436,950,460,687,729,122,382,532,416,315,786,7,782}

658

306

Returns: 102
{255,903,530,604,429,631,703,789,867,830,543,918,490,487,367,237,718,423,282,120,136,371}

450

288

Returns: 49
{985,158,729,632,625,136,86,641,234,897,2,989,584,264,409,279,735,120,526,326,569,590,974}

528

116

Returns: 108
{574,973,561,928,243,215,225,222,166,584,505,642,280,251,327,625,919,828,420,39,382,771,243,438,88,405,773,97,934,752,427,883,427}

20

17

Returns: 964
{233,566,721,490,728,622}

456

363

Returns: 10
{437,571,555,195,323,944,155,889,960,757,612,18,1000,78,899}

698

71

Returns: 117
{392,767,387,742,850,526,280,689,996,502}

284

168

Returns: 40
{176,618,564,243,723,6,119,652,798,211,692,436,528,349,383,141,700,155,287,990,624}

93

79

Returns: 127
{681,783,413,670,56,979,967,858,785,89,202,405,796,906,945,959,306,509,144,893,553,61,935,646,575,932,979,469,460}

367

139

Returns: 139
{252,143,27,983,486,425,966,743,149,80,30,615,723,129,575,627,827,570,794,907,922,763,27,696,468,463,220,423,900,851,476,548,801,319,545,821,710,514,498,338,38,55,832,252,692}

248

1

Returns: 22975
{133,216,59,361,780,995,935,81,811,778,343,316,716,933,728,406}

706

497

Returns: 23
{626,20,284,8,26,787,274,475}

162

105

Returns: 26
{186,955,754,989,507,351,266,365,98,387,860,67,29,803,69,388,504,894,961,599,691,775,880,12,47,729,374,595,9,771,785,386,911,355}

700

9

Returns: 1865
{694,429,948,572,531,905,620,531,302,990,717,372,563,385,745,541,214,968,733,839,560,762,529,8,446,904}

612

1

Returns: 15196
{899,147,151,689,405,932,701,558,718,1000,140,820,111,738,970,955,194,27,552,348,481,12,88,752,460,550,164,779,520,87,849,103,259,287,388,123,838,518,67,676,260}

179

10

Returns: 1928
{663}

481

10

Returns: 19
{990,241,374,163,683,978,52,812,369,647,134,112,855,62,416,798,137,48,450,535,555,76,680,547,636,706,629,527,696,721,505,864,729,778,984}

549

6

Returns: 3003
{848,945,850,128,635,523,416,206,435,637,445,601,502,719,487,534,405,832,297,668,26,541,576,807,826,566,495,617,461,296}

628

7

Returns: 2255
{710}

550

2

Returns: 80
{512,609,410,875,312,442,797,551,485,843,34,662,972,495,837,256,613,714,2,893,815,514,572,28,236,479,116,333,943,512,682,701,959,598,176,246,429,883,535,601}

65

7

Returns: 3104
{356,235,986,617,613,742,556,135,210,621,416,783,326,124,490,86,887,918,948,733,344,311,416,710,231,740,405,381,64,393,830,443,72,5,987,23,498,688,814,871,104,346}

674

6

Returns: 3315
{648,127,90,369,762,367,490,614,33,327,251,554,616,176,437,413,566,320,43,513,320,376,612,641,545,954,172,731,304,789,874,227,134,539,113,660,120,387,706,690,305,434,668,113,780,777,456,92}

762

5

Returns: 4113
{181,663,151,659,572,563,929}

658

1

Returns: 3060
{459,603,256,435,776,869,624,75,811,540,630,965,537,286,353,279,351,212,673,679,951,370,324,2,130,595,339,217,167,357,695}

28

4

Returns: 3644
{185,59}

329

8

Returns: 8
{305,459,112,213,704,250,983,892,717,993}

338

9

Returns: 592
{531,850,121,81,908,681,478,531,807,326,987,705,930,53,742,562,946,473,641,501,250,309,37,521,357}

129

3

Returns: 4407
{385,101,152,243,778,371,120,959,54,943,231,648,179,707,671,926,825,148,19,170,653,863,213,37,527,842,861,410,421,123,704,704,703,702,747,209,342}

523

4

Returns: 4306
{581,351,19,650,547,642,804,859,335,538,509,673,75,364,874,878,635,545,195,309,648,344,213,777,739,464,696,737,957,739,148,909,629,249,161,632,87,595,522,197}

167

10

Returns: 2082
{550,974,703,406,749,758,944,156,300,997,115,492,41,309,539,317,532,109,100}

952

8

Returns: 1025
{39,842,21,127,563,798,807,220,234,5,362,46,225,714,548,988,46,554,48,536,110,165}

574

1

Returns: 7424
{247,164,970,85,603,897,538,105,332,149,631,537,437,327,515,585,765,378,974,432,389,15,660,411,239,507,57,317}

43

9

Returns: 1370
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

2

1

Returns: 49998
{459,494}

1000

999

Returns: 1
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

1000

999

Returns: 98
{352,825,556,40,974,980,215,2,461,73,935,216,333,25,45,558,53,463,718,743,523,641,932,445,697,856,938,886,455,172,848,326,883,336,161,719,655,573}

1000

1

Returns: 18633
{11, 13, 15 }

9

5

Returns: 7
{10, 15 }

12

5

Returns: 3
{1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

2

1

Returns: 49998
{12, 15, 10, 9 }

10

2

Returns: 19
{4, 3 }

5

1

Returns: 3
{4, 7, 10, 5, 6, 55, 2, 22, 35, 42 }

29

5

Returns: 35
{10, 11, 11, 11 }

9

5

Returns: 9
{15, 13, 11 }

9

5

Returns: 7
{20, 21, 22, 23, 5 }

7

5

Returns: 18
{5, 7 }

10

7

Returns: 1
{4, 7, 10, 5, 6, 55, 2 }

20

3

Returns: 26
{10, 9, 10, 10, 10 }

9

5

Returns: 8
{15, 13, 15 }

9

5

Returns: 7
{16, 10 }

10

8

Returns: 2
{1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

2

1

Returns: 30103
{3 }

4

2

Returns: 0
{20, 9 }

9

5

Returns: 4
{10, 16, 23 }

15

8

Returns: 5
{2, 4, 6, 1 }

8

1

Returns: 7
{99, 78, 1, 34, 45, 11, 90, 34, 26, 67, 12 }

45

9

Returns: 54
{1, 2, 3, 4, 5, 6, 7 }

1000

3

Returns: 9
{11, 13 }

10

3

Returns: 5
{2, 12 }

10

4

Returns: 2
{15, 6 }

6

5

Returns: 3
{8, 9 }

5

4

Returns: 3
{1, 1, 1, 1, 3 }

3

1

Returns: 4
{5, 7 }

10

5

Returns: 1
{12, 0 }

12

3

Returns: 0
{4, 4, 4, 4 }

4

3

Returns: 6

Statistics

Problem Statement for "TheJediTestDiv2"

Problem Statement

Definition

Constraints

Examples