Statistics

Problem Statement for "Touchdown"

Problem Statement

In American football, there are two teams. At any one time one team is on offense and the other is on defense. The offense possesses the football and tries to move it toward the defense's goal line while the defense tries to prevent the offense from doing this. If the offense moves the ball beyond the defense's goal line, they score a touchdown. When the offense starts it is given 4 plays which are refered to as "downs". If the ball is moved yardsToGo within those 4 downs, they score a touchdown. If after the 4 downs, the offense failed to score a touchdown and also failed to move the ball at least 10 yards, they lose possession of the ball. If the offense moves the ball 10 or more yards towards the defense's goal line but doesn't score a touchdown, their down count resets to 4; that is no downs carry over and you can never have more than 4 downs at any one time. Each play costs the offense 1 down.

It's fourth quarter, time is running out and your team needs a touchdown to win. Coach has a set of plays that are guaranteed to make a specified number of yards. You will be given an int yardsToGo specifying the number of yards needed to make a touchdown and a int[] plays specifying the number of yards each play will make. Each play can only be run one time to guarantee its effectiveness. You are to return the total minimum number of downs required to make a touchdown or -1 if it is not possible. Note that you cannot exceed yardsToGo by more than 10 because that would put you out of bounds; that is, if you have 43 yardsToGo and no set of plays will advance the ball between 43 and 53 inclusive, you cannot make a touchdown. Also note that you must advance the ball by 10 or more yards to get a fresh set of 4 downs.

Definition

Class:
Touchdown
Method:
howMany
Parameters:
int, int[]
Returns:
int
Method signature:
int howMany(int yardsToGo, int[] plays)
(be sure your method is public)

Constraints

  • yardsToGo will be between 1 and 99, inclusive.
  • plays will contain between 1 and 15 elements, inclusive.
  • Each element in plays will be between 1 and yardsToGo, inclusive.

Examples

  1. 25

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

    Returns: 8

  2. 27

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

    Returns: 11

  3. 27

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

    Returns: 12

  4. 29

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

    Returns: 12

  5. 39

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

    Returns: 15

  6. 28

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

    Returns: -1

  7. 19

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

    Returns: -1

  8. 21

    {10, 10, 11, 5, 6, 5, 1}

    Returns: 2

  9. 19

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

    Returns: 8

  10. 25

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

    Returns: 11

    Doing these plays in this order will get a touchdown: {4, 2, 2, 2}, {3, 3, 2, 2} and {3, 1, 1}.

  11. 10

    {1, 4, 1, 1, 3}

    Returns: -1

  12. 8

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

    Returns: -1

  13. 60

    {1, 20, 20, 31, 39, 59, 59}

    Returns: 2

  14. 60

    {20, 20, 33, 39, 59, 59}

    Returns: -1

    There is no way to get 60 to 70 yards; any 3 plays is greater than 70, and any 2 plays is either less than 60 or greater than 70.

  15. 13

    {9, 1, 1, 1, 1}

    Returns: 5

  16. 30

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

    Returns: 10

    Running plays that get: 8, 3, 3, 3, 3, 3, 3, 2, 1 and 1 will get a touchdown.

  17. 13

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

    Returns: 4

    Running plays that get: {4, 4, 4, (2 or 1)} will get a touchdown!

  18. 72

    {2, 2, 2, 24, 2, 2, 2, 29, 30, 30}

    Returns: 8

  19. 97

    {44, 44, 43, 43, 43, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 11

  20. 10

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

    Returns: 2

  21. 5

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

    Returns: 4

  22. 26

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

    Returns: 3

  23. 6

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

    Returns: 2

  24. 7

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

    Returns: 3

  25. 54

    {20, 10, 11, 22, 14, 3, 18, 24, 46}

    Returns: 2

  26. 79

    {34, 9, 44, 61, 4, 2, 32, 20, 1, 20}

    Returns: 2

  27. 33

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

    Returns: 13

  28. 34

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

    Returns: 14

  29. 96

    {38, 37, 42, 2, 37, 36, 16}

    Returns: 3

  30. 6

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

    Returns: 3

  31. 5

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

    Returns: 4

  32. 26

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

    Returns: 3

  33. 6

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

    Returns: 2

  34. 7

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

    Returns: 3

  35. 54

    {20, 10, 11, 22, 14, 3, 18, 24, 46}

    Returns: 2

  36. 79

    {34, 9, 44, 61, 4, 2, 32, 20, 1, 20}

    Returns: 2

  37. 33

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

    Returns: 13

  38. 34

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

    Returns: 14

  39. 96

    {38, 37, 42, 2, 37, 36, 16}

    Returns: 3

  40. 33

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

    Returns: 15

  41. 64

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

    Returns: 9

  42. 64

    {50, 2, 2, 2, 2, 2, 2, 2}

    Returns: 8

  43. 65

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

    Returns: -1

  44. 30

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

    Returns: 12

  45. 30

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

    Returns: 12

  46. 24

    {6, 3, 1, 4, 4, 1, 1, 1, 1, 1, 1}

    Returns: 11

  47. 24

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

    Returns: 10

  48. 22

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

    Returns: 6

  49. 8

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

    Returns: 4

  50. 24

    {7, 4, 4, 3, 1, 1, 1, 1, 1, 1}

    Returns: 10

  51. 25

    {7, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1}

    Returns: 11

    Here, we can make a touchdown by running the following plays: {1, 1, 3, 7}, {1, 1, 4, 4} and {1, 1, 1}

  52. 10

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

    Returns: -1

  53. 30

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

    Returns: -1

  54. 60

    {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: 15

  55. 45

    {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}

    Returns: 15

  56. 75

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

    Returns: 15

  57. 90

    {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6}

    Returns: 15

  58. 99

    {7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: 15

  59. 65

    {64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64}

    Returns: -1

  60. 12

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

    Returns: -1

    At first glance one might think a touchdown is possible in 6 plays, but note that 10 or more yards cannot be made in 4 plays.

  61. 57

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

    Returns: 15

  62. 54

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

    Returns: 12

  63. 69

    {58, 11, 33, 22}

    Returns: 2

  64. 9

    {1, 1, 1, 6 }

    Returns: 4

  65. 33

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

    Returns: 15

  66. 99

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

    Returns: 8

  67. 25

    {7, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 11

  68. 40

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

    Returns: 3

  69. 99

    {2, 3, 15, 2, 61, 9, 81, 9, 11, 99, 12, 56, 33, 23 }

    Returns: 1

  70. 99

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

    Returns: 9

  71. 99

    {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 99 }

    Returns: 1

  72. 99

    {16, 27, 49, 82, 13, 15, 24, 16, 34, 19, 34, 43, 38, 27, 14 }

    Returns: 2

  73. 32

    {2, 2, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    Returns: -1

  74. 25

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

    Returns: 11

  75. 99

    {98, 98, 40, 59 }

    Returns: 2

  76. 60

    {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

    Returns: 15

  77. 25

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

    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: