Codeforces Solution | 431A: Black Square

Problem Description:

In this problem, phone’s screen is divided into 4 vertical strips. Every second, a black square appears on some of the strips.

Four integers \(a_1, a_2, a_3, a_4 (0 \le a_1, a_2, a_3, a_4 \le 10^4) \) are given. \(a_i\) calories are wasted on touching the \(i^{th}\) strip. (\(a_1\) indicates the calories needed for touching \(1^{st}\) strip, \(a_2\) indicates the calories needed for touching \(2^{nd}\) strip and so on.)

A string \(s (1 \le |s| \le 105)\) is given. \(s\) simply indicates the number of strip where the black square appears. For example, \(s = 112314\) means \(1^{st}\) black square appeared on \(1^{st}\) strip, then on \(1^{st}\) strip again, then on \(2^{nd}\) strip, on \(3^{rd}\) strip, \(1^{st}\) strip and then on \(4^{th}\) strip.

We have to calculate how many calories are needed to destroy all the squares.

Ideological Analysis:

There are 4 strips and \(a_1, a_2, a_3, a_4\) contains the number of calories.

\(s\) contains the strip number where the black square appears. So, simply we can count how many times black square appeared in each strip. And then multiply it with the calories required to touch the strip. We have to do this for all four strips and add them all.

Example:

$$a_1 = 4, a_2 = 1, a_3 = 2, a_4 = 5\space $$ $$and$$ $$s = 2141231$$

Here, Three \(1\)s, two \(2\)s, one \(3\), and one \(4\) in string \(s\). So, we can the total number of calories required to destroy all black squares by weighted sum of them. Such as,

$$ \sum\limits_{i=1}^4 {a_i * COUNT(i)\space in\space s}$$ $$= 3*4 + 2*1 + 1*2 + 1*5 $$ $$= 21$$

Click here for Source Code.