Connection Status:
Competition Arena > Horoscope

Horoscope

SRM 275 · 2005-11-30 · by NeverMore

SRM 275 · 2005-11-30 · by NeverMore · Dynamic Programming
Class Name: Horoscope
Return Type: int
Method Name: maxGoodDays
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

Recently, you went to a fair where one of the attractions was an oracle who would give you your horoscope for the next several days. She wasn't very precise though; all she would say is whether you would have a Good ('G') or Bad ('B') day on a particular day. Besides not being very precise, she was very inconsistent: she could be right AT MOST R times in a row, and she could be wrong AT MOST W times in a row.

Create a class Horoscope, which contains a method maxGoodDays. The method takes a String[] predictions, an int R and an int W as input. The elements of predictions are strings containing only the characters 'G' or 'B', indicating whether your horoscope for that day was predicted to be good or bad. (Note that you should concatenate the elements of predictions and consider the entire string the predictions). The method should return the maximum number of Good days that you can experience given the predictions, and values for R and W.

Constraints

  • predictions will contain between 1 and 50 elements inclusive.
  • Each element of predictions will contain between 1 and 50 characters inclusive.
  • Each element of predictions will contain only the characters 'G' or 'B'.
  • R will be between 1 and 50 inclusive.
  • W will be between 1 and 50 inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{"GGGG"}
4
1
Returns: 4

Since R is 4, the oracle can be Right for all 4 predicted days. In this case, the maximum number of good days you would experience is 4.

1)
{"GGGG"}
2
2
Returns: 3

Here, the oracle can't be Right for all 4 days. One way of achieving 3 Good days (which is the maximum possible in this case) is for the oracles predictions to be Right, Wrong, Right, Right for the 4 days respectively. Thus, the return value here is 3.

2)
{"GBGBBB"}
3
4
Returns: 6
3)
{"GGGBBBGBGGGB", "GGBBBBBBBBBGBGBGBGBGBGBGBGBBBBBBBBBBBBBBGGGG", "G"}
4
35
Returns: 56
4)
{ "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB",
            "GGBGBGBGBGBGBGBGBGBGGGGGGGGGGGBGBGBBBBBBBGGGGGGBGB"}
50
50
Returns: 2450

Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Horoscope with a public method int maxGoodDays(vector<string> predictions, int R, int W) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous