Moons and Umbrellas solution codejam 2021

### Problem

Cody-Jamal is working on his latest piece of abstract art: a mural consisting of a row of waning moons and closed umbrellas. Unfortunately, greedy copyright trolls are claiming that waning moons look like an uppercase C and closed umbrellas look like a J, and they have a copyright on CJ and JC. Therefore, for each time CJ appears in the mural, Cody-Jamal must pay XX, and for each time JC appears in the mural, he must pay YY.

Cody-Jamal is unwilling to let them compromise his art, so he will not change anything already painted. He decided, however, that the empty spaces he still has could be filled strategically, to minimize the copyright expenses.

For example, if `CJ?CC?`

represents the current state of the mural, with `C`

representing a waning moon, `J`

representing a closed umbrella, and `?`

representing a space that still needs to be painted with either a waning moon or a closed umbrella, he could finish the mural as `CJCCCC`

, `CJCCCJ`

, `CJJCCC`

, or `CJJCCJ`

. The first and third options would require paying X+YX+Y in copyrights, while the second and fourth would require paying 2⋅X+Y2⋅X+Y.

Given the costs XX and YY and a string representing the current state of the mural, how much does Cody-Jamal need to pay in copyrights if he finishes his mural in a way that minimizes that cost?

### Input

The first line of the input gives the number of test cases, TT. TT lines follow. Each line contains two integers XX and YY and a string SS representing the two costs and the current state of the mural, respectively.

### Output

For each test case, output one line containing `Case #xx: yy`

, where xx is the test case number (starting from 1) and yy is the minimum cost that Cody-Jamal needs to pay in copyrights for a finished mural.

### Limits

Time limit: 10 seconds.

Memory limit: 1 GB.

1≤T≤1001≤T≤100.

Each character of SS is either `C`

, `J`

, or `?`

.

#### Test Set 1 (Visible Verdict)

1≤1≤ the length of SS ≤10≤10.

1≤X≤1001≤X≤100.

1≤Y≤1001≤Y≤100.

#### Test Set 2 (Visible Verdict)

1≤1≤ the length of SS ≤1000≤1000.

1≤X≤1001≤X≤100.

1≤Y≤1001≤Y≤100.

### Extra credit!

What if some copyright holders could pay Cody-Jamal for the advertisement instead of being paid? Cody-Jamal getting paid is represented by a negative cost.

#### Test Set 3 (Hidden Verdict)

1≤1≤ the length of SS ≤1000≤1000.

−100≤X≤100−100≤X≤100.

−100≤Y≤100−100≤Y≤100.

### Sample

*Note: there are additional samples that are not run on submissions down below.*

Sample Input

4 2 3 CJ?CC? 4 2 CJCJ 1 3 C?J 2 5 ??J???

Sample

Output

Case #1: 5 Case #2: 10 Case #3: 1 Case #4: 0

Sample Case #1 is the one explained in the problem statement. The minimum cost is X+Y=2+3=5X+Y=2+3=5.

In Sample Case #2, Cody-Jamal is already finished, so he does not have a choice. There are two `CJ`

s and one `JC`

in his mural.

In Sample Case #3, substituting either `C`

or `J`

results in one `CJ`

either from the second and third characters or the first and second characters, respectively.

In Sample Case #4, Cody-Jamal can finish his mural with all `J`

s. Since that contains no instance of `CJ`

nor `JC`

, it yields no copyright cost.

### Additional Sample – Test Set 3

*The following additional sample fits the limits of Test Set 3. It will not be run against your submitted solutions.*

Sample

Input

1 2 -5 ??JJ??

Sample

Output

Case #1: -8

In Sample Case #1 for Test Set 3, Cody-Jamal can finish his mural optimally as `JCJJCC`

or `JCJJJC`

. Either way, there is one `CJ`

and two `JC`

s in his mural.

**Solution: **

include <bits/stdc++.h>

using namespace std;

void solve(int t){

cout << “Case #” << t << “: “; int x, y; string s; cin >> x >> y >> s;

int n = (int)s.size();

vector > dp(n+1, vector(2, 1e9));

dp[0][0] = dp[0][1] = 0;

for(int i = 1; i <= n; i++){ for(int c = 0; c < 2; c++){ if(c == 0 && s[i-1] == ‘J’) continue; if(c == 1 && s[i-1] == ‘C’) continue; for(int d = 0; d < 2; d++){ int cost = 0; if(i > 1){

if(d == 0 && c == 1) cost += x;

if(d == 1 && c == 0) cost += y;

}

dp[i][c] = min(dp[i][c], dp[i-1][d] + cost);

}

}

}

cout << min(dp[n][0], dp[n][1]) << ‘\n’;

}

int main(){

ios_base::sync_with_stdio(false), cin.tie(nullptr);

int T;

cin >> T;

for(int t = 1; t <= T; t++) solve(t);

}

Also Read:

import sys

def solve(x, y, s):

dp = {}

if s[0]==’C’:

dp[(0, ‘C’)] = 0

dp[(0, ‘J’)] = float(‘inf’)

if s[0]==’J’:

dp[(0, ‘J’)] = 0

dp[(0, ‘C’)] = float(‘inf’)

if s[0]==’?’:

dp[(0, ‘C’)] = 0

dp[(0, ‘J’)] = 0

for i in range(1, len(s)):

if s[i]==’C’:

dp[(i, ‘C’)] = min(y + dp[(i-1, ‘J’)], dp[(i-1, ‘C’)])

dp[(i, ‘J’)] = float(‘inf’)

elif s[i]==’J’:

dp[(i, ‘J’)] = min(x + dp[(i-1, ‘C’)], dp[(i-1, ‘J’)])

dp[(i, ‘C’)] = float(‘inf’)

elif s[i]==’?’:

dp[(i, ‘C’)] = min(y + dp[(i-1, ‘J’)], dp[(i-1, ‘C’)])

dp[(i, ‘J’)] = min(x + dp[(i-1, ‘C’)], dp[(i-1, ‘J’)])

return min(dp[(len(s)-1, ‘J’)], dp[(len(s)-1, ‘C’)])

# parse input and solve

i = iter(sys.stdin)

N = int(next(i))

cases = []

while N>0:

N-=1

c = next(i)

if c[-1]==’\n’: c = c[:-1]

cases +=[c.split(‘ ‘)]

for i, c in enumerate(cases):

x = int(c[0])

y = int(c[1])

s = c[2]

cost = solve(x, y, s)

print(‘Case #%i: %i’ % (i+1, cost))