Statistics

Problem Statement for "SimpleIO"

Problem Statement

Consider a simple Input/Output system. The system input consists of a button that you can press, while the system output consists of an audible beep. The system logic consists of a state machine that transitions from one state to the next every time the button is pressed. At the last state, the machine transitions to the first state when the button is pressed. On some state transitions, the audible beep is sounded, and on others it is not. The pattern of beeps mapped to states is known ahead of time.

You are given a String pattern of beeps for state transitions. The i-th character of pattern (0-based index) will be a 'B' if there is a beep when state i is entered, and will be a 'N' if there is no beep. You are also given an int targetState to achieve, but not the starting state. Return the worst case scenario of the most number of times you must press the button to guarantee the machine is in the targetState. If it is not possible to always ensure you can end on the targetState, return -1.

Definition

Class:
SimpleIO
Method:
worstCase
Parameters:
String, int
Returns:
int
Method signature:
int worstCase(String pattern, int targetState)
(be sure your method is public)

Constraints

  • pattern will have between 2 and 50 characters, inclusive.
  • pattern will only contain the characters 'B' and 'N'.
  • targetState will be between 0 and the length of pattern - 1, inclusive.

Examples

  1. "BNB"

    0

    Returns: 4

    In the worst case, the first state is state 2. In this case, you press the button 2 times before we narrow down that the state is now state 1. You must now press the button 2 more times to get back to state 0.

  2. "BNBNBNBN"

    3

    Returns: -1

    In this case, we can only tell if we are on an even or odd state, we cannot determine the exact state.

  3. "BBNNBNBBBBNBBBBBB"

    3

    Returns: 18

  4. "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBN"

    48

    Returns: 98

  5. "BNNBNNBNNBNNB"

    6

    Returns: 20

  6. "BNBBNBBBNBBBBNBBBBBNBBBBBBN"

    15

    Returns: 34

  7. "BBBBNNNBBNBBBNNNNNBNBBNBBBBBNNNBBNBBBNNNNNBNBBNB"

    4

    Returns: -1

  8. "BBBBNNBBBBNNBBBBNNBBBBNNBBBBNN"

    21

    Returns: -1

  9. "NBBBBNNBNNBNNBNBBBBNNBNNBNNBNBBBBNNBNNBNNB"

    28

    Returns: -1

  10. "NBBNBBBBBNNBBBBBNBNNN"

    13

    Returns: 25

  11. "NNNNNNBNNNNNNN"

    0

    Returns: 22

  12. "BBNBBNBBBBNBNNNNNBBBBBBNBBBB"

    0

    Returns: 34

  13. "BNNBNNNNNNNNBBNNNBNNNNNBNBBB"

    4

    Returns: 32

  14. "NNBNNBBNNBNNBNBNBBBBNBBNBN"

    4

    Returns: 31

  15. "BNBBNNNNNBB"

    1

    Returns: 14

  16. "BBNBBBNBBNBBBNBBNBBBNBBNBBBN"

    16

    Returns: -1

  17. "NBBBNNNBNBNNNBBNNBBNNNB"

    6

    Returns: 28

  18. "NBBBNBNN"

    2

    Returns: 10

  19. "NBNNNBBNBBNNNBNNNNBNNNBBNBBNNNBNNN"

    23

    Returns: -1

  20. "NNBNBNNBBBNNBNBBNNBNBNNBBBNNBNBBNNBNBNNBBBNNBNBB"

    25

    Returns: -1

  21. "NNBBNNNNNBBBBBNNNNNNBBNNNNNBBBBBNNNN"

    28

    Returns: -1

  22. "NBBNNBNNBBNBNNNNNBNNNBBBBNNNNBNNBNBNBNNBNNNNN"

    35

    Returns: 50

  23. "BBNNBBNNBBNNBBNNBBNNBBNNBBNNBBNNBBNN"

    1

    Returns: -1

  24. "BBNBNBNNNBBBNBBNNNNBBNNBNBBNBNNBBNNBBBNB"

    7

    Returns: 45

  25. "BNNNNBNB"

    7

    Returns: 10

  26. "BNNBNNBNBNBBNNNNBNBBNBBBBBBNBNNNNNBBBBBBBNNBN"

    40

    Returns: 51

  27. "NNNNBBBBBNNNBNBBBNNNBN"

    19

    Returns: 28

  28. "NNBNNBBBBNNNNNBNNBBBBNNN"

    0

    Returns: -1

  29. "BNBNNBNBNBBBNBBNBBNNBNNBNBNNBNBNBBBNBBNBBNNBNN"

    18

    Returns: -1

  30. "NNBBNBNNBNNNBBNBNNBNNNBBNBNNBNNNBBNBNNBN"

    13

    Returns: -1

  31. "BNBBBBNBBNNNBNBBBBNBBNNNBNBBBBNBBNNNBNBBBBNBBNNN"

    19

    Returns: -1

  32. "NNNBNNNNNBNNNNNBNN"

    5

    Returns: -1

  33. "BBNNBNBNNNBBBBBBNNBBNNBNBNNNBBBBBBNN"

    12

    Returns: -1

  34. "BBNN"

    1

    Returns: 5

  35. "NBNNBNNBNBNNBNNBNBNNBNNBNBNNBNNBNBNNBNNB"

    0

    Returns: -1

  36. "BNBNNNBNBNBNNNBNBNBNNNBNBNBNNNBN"

    31

    Returns: -1

  37. "NNNNNNBNNBBNNBBNB"

    12

    Returns: 20

  38. "BNBBBNBBNNBNNBBNBNNNBNNBBBNBBBNNBNNNBBBNN"

    30

    Returns: 47

  39. "NNBNNBNNNBNBNNBBNNBNBNNNBNNBNNNBNBNNBBNNBNBN"

    42

    Returns: -1

  40. "BBBNNNNNNBBBNNNNNNBBBNNNNNNBBBNNNNNN"

    13

    Returns: -1

  41. "NNBBNBNBN"

    7

    Returns: 12

  42. "NBBNNBBBNNBBNBBNNBNBBBBBNBBB"

    19

    Returns: 31

  43. "BNNBBNBBNBBNBNNBBNNBBBB"

    22

    Returns: 27

  44. "NBNNNNBNBBNBBBNBBBNNNBNNBNNNNBNBBNBBBNBBBNNNBN"

    27

    Returns: -1

  45. "BNNNBBBBNBNNNNNNNNNBNBNNNBBBBNBNNNNNNNNNBN"

    20

    Returns: -1

  46. "BBBBBBBBBBBB"

    8

    Returns: -1

  47. "NNNNNNNNNBBBNNNNNNNNNBBB"

    18

    Returns: -1

  48. "NBNBBNNNBNBBNNBNNNNBNNBNBBBNNBNBBNNNBBBBNB"

    31

    Returns: 48

  49. "NNBNNNBBNNBBNNBBBBNNBNBBNBBNBNNBBNBN"

    20

    Returns: 41

  50. "NBBBNBBNBNBBBNBBNBNBBBNBBNBNBBBNBBNBNBBBNBBNB"

    37

    Returns: -1

  51. "BBBNBBBNBBNNNBNBBNBNNBBBNBNN"

    27

    Returns: 34

  52. "NBNNBBBBBBNBBBNNNNNNNNNBNNBBBBBBNBBBNNNNNNNN"

    10

    Returns: -1

  53. "NNBBNNBBNNBNBNBNNBBNNBBNNBNBNBNNBBNNBBNNBNBNB"

    22

    Returns: -1

  54. "BBBNBNBNBN"

    3

    Returns: 12

  55. "BBNNNBBBBBNBNNNBBNBBNNNBBBBBNBNNNBBN"

    4

    Returns: -1

  56. "BNBNBNBNBNBNBNBNBNBN"

    17

    Returns: -1

  57. "NBNBNNB"

    1

    Returns: 11

  58. "BBNBNBBBBNNBNBBBNBNBNBNBBBBBBBBBNNNNBNBNBBBBBBBBNN"

    44

    Returns: 60

  59. "BNNBNNBNN"

    3

    Returns: -1

  60. "BN"

    0

    Returns: 2

  61. "BBBBBBBBBNBB"

    0

    Returns: 15

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: