Statistics

Problem Statement for "FoxAndVacation"

Problem Statement

Fox Ciel is planning to visit the Tourist Kingdom for total days. This kingdom is full of lovely cities. During her stay Ciel would like to visit as many different cities as possible. She cannot visit more than one city on the same day.


Additionally, different cities may require her to stay for a different number of days. For each i, city i only counts as visited if Ciel spends at least d[i] days in the city.


You are given the int total and the int[] d. Return the maximal number of cities she can visit during her vacation.

Definition

Class:
FoxAndVacation
Method:
maxCities
Parameters:
int, int[]
Returns:
int
Method signature:
int maxCities(int total, int[] d)
(be sure your method is public)

Notes

  • When solving the task, ignore travel times. (Fox Ciel always travels at night, and she can travel between any two cities very quickly.)

Constraints

  • total will be between 1 and 50, inclusive.
  • d will contain between 1 and 50 elements, inclusive.
  • Each element of d will be between 1 and 50, inclusive.

Examples

  1. 5

    {2,2,2}

    Returns: 2

    Fox Ciel's vacation lasts for 5 days. She needs at least 2 days to visit each of the cities, so she can visit at most 2 of them.

  2. 5

    {5,6,1}

    Returns: 1

    She can only visit one city: either city 0, or city 2.

  3. 5

    {6,6,6}

    Returns: 0

    This time the poor Fox Ciel cannot visit any city during her summer vacation.

  4. 6

    {1,1,1,1,1}

    Returns: 5

    In this test case Ciel can visit all five cities. Note that at the end of her trip each city either does count as visited, or it does not -- there is no way to "visit" the same city twice.

  5. 10

    {7,1,5,6,1,3,4}

    Returns: 4

  6. 50

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

    Returns: 9

  7. 21

    {14,2,16,9,9,5,5,23,25,20,8,25,6,12,3,2,4,5,10,14,19,12,25,15,14}

    Returns: 6

  8. 14

    {11,4,3}

    Returns: 2

  9. 50

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 50

  10. 38

    {15,12,17,11,23,19,6,19,30,19,13,27,23,12,3,14,18,22,35,36,4}

    Returns: 5

  11. 13

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 13

  12. 32

    {1,1,2,2,2,2,1,1,1,1,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,1,1}

    Returns: 20

  13. 16

    {5,8,17,13,15,13,23,7,15,5,23,10,2,13,20,5,1,21,6,10,8,25,2,20,2,12,13,25,25,24,24,21,13,11,3,18,2,5,5,12,6,11,8,6,6,1,23}

    Returns: 7

  14. 10

    {1,37,6,37,45,38,6,47,41,42,40,30,15,9,40,41,12,37,24,17,12,47,28,17,3,10,32,8,26,39,6,16,9,46,24,29,16,2,24,10,27,3,4,44,14,47}

    Returns: 4

  15. 49

    {1,1,1,3,1,1,1,2,3,1,3,1,3,1,3,3,1,3,1,1,3,3,1,2,3,3}

    Returns: 25

  16. 18

    {14,13,3,10,6,11,4,1,16,2,16,3,11,5,9,14,8,18,13}

    Returns: 6

  17. 4

    {15,18,9,2,21,20,20,14,24,33,3,33,5,3,1,31,19,21,23,29,6,14,15,3,24,29,33,21,13,7,20,30,26,33,18,19,22,3,11,21,32,30}

    Returns: 2

  18. 25

    {1,6,2,4,3,3,6,2,7,2,3,5,1,1,1,1,4,6,5,2,4,5,5,4,4,3}

    Returns: 13

  19. 48

    {4,5,2,3,5,5,3,1,3,5,5,5,4}

    Returns: 12

  20. 23

    {5,32,6,12,2,22,9,11,26,7,20,5,24,31,19,6,33,11,29,6,29,3}

    Returns: 5

  21. 47

    {9,31,32,15,13,27,19,9,10,9,14,20,25,8,6,8,10,14,7,19,18,27,1,30}

    Returns: 6

  22. 46

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 23

  23. 39

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

    Returns: 10

  24. 18

    {20,5,11,21,20,14,3,15,17,4,6,4,11,16,23}

    Returns: 4

  25. 31

    {20,3,6,17,12,1,1,10,18,18,18,8,4,11,11,12}

    Returns: 6

  26. 16

    {8,3,5,5,14,7,8,1,10,9,5,6,10,3,1,7,5,10,12,15,12,1,9,1,14,6,4,3,7,2,15,5,2,14,13,9,5,13,16,11,7,15,10}

    Returns: 8

  27. 28

    {1,1,1}

    Returns: 3

  28. 33

    {12,4,13,20,10,4}

    Returns: 4

  29. 50

    {14,14,8,11,16,4,15,19}

    Returns: 4

  30. 3

    {11,9,26,20}

    Returns: 0

  31. 43

    {6,34,4,44,14}

    Returns: 3

  32. 26

    {24,10,7,40,32,18,7,24,40,35,19,32,16,28,17,29,38,2,2,20,33,16,6,24,30,25,5,20,34,26,12}

    Returns: 5

  33. 22

    {11,4,28,20,30,3,3,1,27,1,14,14,27,27,22,2,21,18,30,23,31,3,26,15,20,28,6,11,17,11,13,23,10,7}

    Returns: 7

  34. 37

    {5,1,3,6,8,12,13,3,5,3,3,6,8,12,3,9,4,2,5,5,8,9,1,9,3,5,4,7}

    Returns: 12

  35. 39

    {12,12,3,15}

    Returns: 3

  36. 46

    {3,4,2,1,3,3,3,4,1,4,1,1,1,2,3,4}

    Returns: 16

  37. 42

    {17,3,6,9,8,16,10,6,2,15,9,3,14,22,1,22,8,13,20,3,19,17,6,16,22,1,1,8,6,17,5,5,17,18}

    Returns: 12

  38. 22

    {8,1,1,2,6,4,4,4,2,3,10,2,9,1,5,8,2,1,2,3,9,1,10,1,9,7,8,4,6,2,9,2,7,4,7,7,5,5,4,7,8,8,7,10}

    Returns: 13

  39. 37

    {28,31,27}

    Returns: 1

  40. 17

    {8,5,14,10,13}

    Returns: 2

  41. 43

    {8,17,10,2,22,7,17,15,13,14,16,4,10,18,22,11,11,22,8,17,11,10,9,8,11,12,20,4,9,19,2,5,8,13,5,3,19,19,22,18,11,7,13,17,21,8,8}

    Returns: 9

  42. 14

    {2,2,2,2,2,1,2,1,2,2,1,1,2,1,2,1,2,1,2,2,1,1,1,2,2,1,2,1,1,1}

    Returns: 14

  43. 39

    {4,2,4,10,6,4,1,6,6,10,10,11,10,3,4,11,10,3,4,10,5,9,6,9,8,7,4,1,2,2,9,3,9,3,8,4,1,11,7,3,6,10,6,10,10,1}

    Returns: 15

  44. 25

    {26,5,32,4,7,37,30}

    Returns: 3

  45. 15

    {1,2,3,5,1,5,2,1,5,2,1,4,4,4,2,7,7,5,6}

    Returns: 9

  46. 13

    {6,3,1,1,4,2,3,2,2,5,4,3}

    Returns: 6

  47. 27

    {28,21,2,16,18,16,9,5,1,12,17,23,22,20,15,16,1,20,25,22,6,22,15,28,9,14,25,8,14}

    Returns: 6

  48. 28

    {13,21,12,4,1,17,13,6,9,5,3,8,1,13,4,12,16,13,10,23,11,19,23,11,16,13,3,22,12,6,20,23,10,17,9,24,7,21}

    Returns: 8

  49. 49

    {1,2,2,1,2,1,2,2,1,1,1,1,2,2,2,2}

    Returns: 16

  50. 32

    {21,17,9}

    Returns: 2

  51. 50

    {2,10,10,8,6,6,6,6,7,5,11,7,8,5,6,1,4,4,10,11,11,1,3,2,2,8,1,6,1,2,11,4,6,9,2,5,11,3,11,4}

    Returns: 17

  52. 24

    {5,2,7,9,11,6,2,3,1,6,8,4,11,2,10,11,7,11,7,8,7,8,8,3,11,7,10,7,6,10,5,7,9,8,7,9,8,11,3,10,8,3,2,6}

    Returns: 9

  53. 40

    {13,14,2,15,1,12,6,6,16,16,8,11,11,15,8,5,12,5,7,17,8,11,1,7,13}

    Returns: 9

  54. 45

    {30,13,4,24,15,13,17,10,12,13,29,14,28,28,15,28,8,2,27,17,5,24,27,13,25,4,7,4,1,15,29,19,20,29,9,5,6,15,15,20,11,26,29,20,7,12,24}

    Returns: 10

  55. 13

    {5,10,3,5,11,17,11,12,3,11,6,13,3,12,2,17,5,2,8,11,13,6,3,10,1,10,8,4,16,6,5,15,2,14,11,4,3}

    Returns: 6

  56. 39

    {3,11,11,2,6,7,8,4,11,13,2,12,5,6,3,11,1,1,8,7,8,9,8,4,5,7,11,1,7,11,13,5,3,1,5,10,13,5,10,10}

    Returns: 13

  57. 14

    {15,10,18,3,6,1,15,2,4,4,11,6,5,15,5,6,1,7}

    Returns: 5

  58. 24

    {10,2,9,3,2,3,6,2,8,2,9,5,4,2,2,3,9,6,6,3,4,3,5,7,3,2,10,5,4,9,9,1,5,8,5}

    Returns: 11

  59. 28

    {3,2,2,1,3,3,2,2,1,3,2,3,1,1,3,3,3,3,3,1,2,2,1,2,2}

    Returns: 16

  60. 35

    {47,36,22,27,16,26,5,50,10,2,7,24}

    Returns: 4

  61. 44

    {17,23,6,16,15,2,13,29,28,24,21,1,12,28,27,27,19,18,25,22,25,26,17,1,17,6,24,21,6,19,14,26,9}

    Returns: 8

  62. 46

    {28,14,23,22,30,30,20,6,32,23,30,9}

    Returns: 3

  63. 14

    {30,17,26,31,33,19,16,16}

    Returns: 0

  64. 10

    {9,23,9,31,36,37,14,8,21,7,43,16,21,40,7}

    Returns: 1

  65. 14

    {14,9,2,15,4,9,10,8,5,19,26,26,7,8,13,21,13,2}

    Returns: 4

  66. 11

    {10,9,4,8,5,12,1,6,7,3,6,2,2,14,11,15,6,8,6,3,10,13,13,6,16,14,16,2,4,13,6,14,7,10}

    Returns: 5

  67. 42

    {7,1,3,8,3,3,1,2,3,7,13,6,3,6,3,14,12,9,8,6,13,5,6,7,7,4,6,4,14,7,6,8,3,11,12,3,3,14,13,9,14}

    Returns: 14

  68. 29

    {23,4,22,11,12,12,12,21,17,12,23,15,20,7,21,11,13,11}

    Returns: 3

  69. 34

    {19,6,1,1,10,19,16,18,15,22,8,5,3,2,1,16}

    Returns: 8

  70. 5

    {7,1,2,3,8,4,4}

    Returns: 2

  71. 22

    {6,12,18,22,19,14,8,3,36,15,25,20,30,28,8,33,31,22,7,14,10,19,13,3,17,1,19,11,30,6,8,8,19,27,20,27,38}

    Returns: 5

  72. 49

    {3,12,2,8,30,5,2,27,13,7,12,9,28,13,23,17,20,23,27,25,14,27,4,2,9,21,29}

    Returns: 9

  73. 27

    {7}

    Returns: 1

  74. 26

    {12,8,6,6,4,1,1,9,2,1,9,12,13,3,3,4,11,11,3,5,7,10,8,10,13,6,7,3,10,5}

    Returns: 10

  75. 28

    {15,14,28,39,25,8,12,18,2,33,28,31}

    Returns: 3

  76. 19

    {39,23,16,30,32,6}

    Returns: 1

  77. 19

    {19,13,16,18,11,14,4,2,16,17,11,18,14,13,8,5,1,6,13,6,2,17,6,3,19,19,2,20,14,3,16,4,15,11,3,2,11,10,5,12,14,13,19,11,4,15}

    Returns: 8

  78. 6

    {16,18,31,21,29,14,5,29,1,30,30,24,18,17,42,4,14,41,11,39,6,11,22,31,16,13,24,31,42,33,13,25,7,19,41,22,13,4,11,8,21,22,33}

    Returns: 2

  79. 34

    {40,18,14,2,41,5,14,6,6,20,5,10,36}

    Returns: 6

  80. 13

    {1,23,14,13,7,10,15,5,20,19,25,13,28,27,16,29,22,18,26,1,2,22}

    Returns: 4

  81. 46

    {14,15,16,1,16,7,17,3,16,12,17,7,16,11,12,4,13,3,4,12}

    Returns: 8

  82. 23

    {44,36,20,18,38,26,1,5,5,12,20,32,39,21,40,34,26,21,43,21,11,38,37,6,19,27,43,47,14,5,42,17,19,22,30,28,33,35,29}

    Returns: 5

  83. 46

    {8,8,6,3,3,6,3,8,7,11,10,10,7,7,2,3,6,1,7,3,9,6,11,5,9,8,1}

    Returns: 12

  84. 22

    {3,2,2,1,3,3}

    Returns: 6

  85. 49

    {15,7,3,6,15,5,5,1,2,15,5,8,3,15,12,12,11,6,10,8,10,11,7,3,1,11,8,13,6}

    Returns: 12

  86. 44

    {14,33,14,28,14,1,19,26,15,30,5,12,22,9,13,4,14}

    Returns: 6

  87. 32

    {19,12,13,8,3,10,10,4,9,5,2,3}

    Returns: 6

  88. 42

    {13,21,18,6,10,17,5,9,8,9,12,19,1,12,8}

    Returns: 6

  89. 5

    {16,25,13,23,7,20,13,9,12,28,8,21,22,6,9,7,30,2,14,10,21,7,10,24,17,3,14,9,16,18,12,9,11,15,20,5}

    Returns: 2

  90. 12

    {26,6,6,27,19,1,4,6,27,5,12,1,29,14,6,3}

    Returns: 4

  91. 12

    {15,26,11,9,1,2,25}

    Returns: 3

  92. 43

    {10,4,10,13,8,4,9,9,10,9,12,5,11,12,9,10,4,3,7,13,12,1,4,7,7,2,9,4,12,11,5,2,13,13,3,5,12,7,9,2,4}

    Returns: 13

  93. 18

    {21,15,19,38,40,40,29,26,34,11,33,32,14,6,2,35,24,25,3,14,22,10,27,13,29,10,5}

    Returns: 4

  94. 21

    {31,26,13,5,6,26,21,11,7,5,4,15,28,29,25,26,30,20,22,30,12,1,19,7,8,18,34,11,29,15,32,20,19,30,29,26,10,7,18,2,8,19,6,23,18,19}

    Returns: 5

  95. 38

    {8,4,6,6,8,2,2,3,2,5,4}

    Returns: 9

  96. 45

    {2,7,11,17,2,9,18,16,16,8,5,18,5,17,16,5,4,13,16,10,9,3,18,15,9,5,14,7,11,3,6,17,9,7}

    Returns: 10

  97. 37

    {2,1,21,25,10,18,2,30,21,27,14,8,8,9,30,7,14,28,9,12,14,17,7,25,26,11,24,29,14,31,25,18,30,8,12,31}

    Returns: 7

  98. 45

    {3,1,3,2,1,3,2,2,1,2,3,3,2,3,3,2,3,3,3,3,2,2,2,2,2,3,1,2,3,2,3,1,3}

    Returns: 22

  99. 12

    {25,21,26,8,8,21,1,6,28,2,6,14,10,8,26,10,11,15,6,10,17,3,26,29,24,5,11,27,14,25,4}

    Returns: 4

  100. 7

    {50,32,39,40,19,49,25,46,7,29,12,23,19,17,12,15,41,36,26,45,16,2,3,9,13}

    Returns: 2

  101. 37

    {33,1,21,29,12,11,30,4,3,41,7,38,2,8,15,34,29,19,42,12,27,22}

    Returns: 7

  102. 44

    {18,17,7,28,29,9,6,17,26,7,11,28,14,11,27,31}

    Returns: 5

  103. 45

    {19,20,2,1,6,20,13,7,2,22,8,21,19,9,22,22,19,20,3,8,6,8,15,4,5,5,19,14,11,5,17,7,22,2}

    Returns: 11

  104. 44

    {29,13,17,33,31,7,36,17,20,39,13,8,30,36,25,6,13,35,13,34,27,40,25,40,35,21}

    Returns: 4

  105. 38

    {33}

    Returns: 1

  106. 45

    {23,19,15,24,34,27,17,18,6,35,17,4,23,34,8,32,32,19,10,16,2,21,32,30,4,22}

    Returns: 6

  107. 9

    {1, 2, 3, 6 }

    Returns: 3

  108. 1

    {1 }

    Returns: 1

  109. 5

    {5 }

    Returns: 1

  110. 10

    {2, 2, 2, 2, 2 }

    Returns: 5

  111. 21

    {14, 2, 16, 9, 9, 5, 5, 23, 25, 20, 8, 25, 6, 12, 3, 2, 4, 5, 10, 14, 19, 12, 25, 15, 14 }

    Returns: 6

  112. 2

    {1, 1, 1 }

    Returns: 2

  113. 6

    {1, 1, 1, 1, 1 }

    Returns: 5

  114. 10

    {7, 1, 5, 6, 1, 3, 4 }

    Returns: 4

  115. 50

    {1, 1 }

    Returns: 2

  116. 50

    {1 }

    Returns: 1

  117. 10

    {2, 2, 2, 2 }

    Returns: 4

  118. 5

    {1, 1, 1, 1, 1 }

    Returns: 5

  119. 6

    {5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 6

  120. 5

    {2, 2, 2 }

    Returns: 2

  121. 5

    {2, 2, 1 }

    Returns: 3

  122. 5

    {1, 1, 1, 1, 1, 1, 1 }

    Returns: 5

  123. 50

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 50

  124. 3

    {3 }

    Returns: 1

  125. 10

    {1 }

    Returns: 1

  126. 6

    {1 }

    Returns: 1

  127. 2

    {2 }

    Returns: 1

  128. 10

    {1, 2, 3 }

    Returns: 3

  129. 10

    {9, 1, 2, 3, 4 }

    Returns: 4

  130. 50

    {1, 2 }

    Returns: 2

  131. 12

    {5, 7, 3 }

    Returns: 2

  132. 50

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 10

  133. 5

    {2, 1 }

    Returns: 2

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: