# Problem Link

# Difficulty

CakeWalk

# Pre-requisites

Basic programming language constructions

# Problem

Find the maximal value of the profit for playing a single-player game described in the problem statement

# How to get 20 points

Let’s generate all permutations of the order of the questions and calculate the score for each of them. Among the scores for all the orders, choose the maximal. Then just output the maximal obtained score. Since there are exactly **N!** permutations of the set of **N** questions and a check of a single order takes **O(N)** time, the complexity of such a solution is **O(N!*N)**.

In C++ you can use STL routine next_permutation for simple generation of all the permutations.

This solution solves the first subtask, however, it is too slow to get the full points.

# How to get 100 points

Let us calculate **K** - the number of the questions that would be answered correctly by Chef. Clearly, the **i**^{th} question will be answered correctly if the **i**^{th} sumbol in the first string equals to the **i**^{th} symbol in the second string.

If **K = N**, there is no other option than Chef answers all the questions correctly and gets **W _{N}** dollars of profit.

Otherwise, using any question than can be answered incorrectly, we can obtain any number of correct answers between **0** and **K** inclusively. Then the answer is, therefore, the maximal value of **W _{i}** for

**0 ≤ i ≤ K**.

The complexity of such a solution is **O(N)** for a single test case.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here