### PROBLEM LINK:

**Author:** Vitalij Kozhukhivski

**Tester:** Sergey Kulik

**Editorialist:** Adury Surya Kiran

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Basics like iterating loops in any programming language.

### PROBLEM:

Given a piano keyboard which contains **12 * N** keys, and a pattern to play. If you are currently at **x**th key, then if you encounter **‘S’** in the pattern you should move to **x** + 1th key, else if you encounter a **‘T’** in the pattern then you should move to **x** + 2th key. You can start playing from any of the **12 * N** keys. In one play, you can repeat the pattern as many times as you want, but you cannot go outside the keyboard.

You are asked to calculate number of different plays that can be performed. Two plays differ if and only if they start at different keys or patterns are repeated different number of times.

### EXPLANATION:

Direct brute-force would pass for this question, find out how many times you can repeat the pattern from each starting position and add it to the answer.

**C++ Code**

```
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
// we use 'cas' because 'case' is a keyword
int N;
string s;
cin >> s;
cin >> N;
int ans = 0;
for(int x, y, sp = 0; sp < 12 * N; sp++){
y = sp;
while(true){
x = y;
for(int i = 0; i < s.length(); i++){
x += s* - 'R';
}
if(x >= 12 * N){
break;
}
y = x;
ans++;
}
}
cout << ans << ’
```

’;

}

}

Complexity : **O( N * N * T * |S|)**

We can have one optimization like this, rather than iterating through S every time we can do it only once in the beginning and store how much x is incremented in each complete play.

That brings the complexity down to **O(N * N * T)**.

### ALTERNATIVE SOLUTION:

We can iterate through number of times the pattern is repeated and find out how many starting positions can be possible for each respective number of repetitions.

One observation we can make here is, if we have the length of play, then number of starting positions will be **12 * N – L**, where **L** is the length of the play. It is easy to prove it, reader is encouraged to prove it.

**C++ Code**

```
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
// we use 'cas' because 'case' is a keyword
int N, l = 0;
string s;
cin >> s;
cin >> N;
int ans = 0;
for(int i = 0; i < s.length(); i++){
l += s* - 'R';
}
for(int p = l; p < 12 * N; p += l){
ans += 12 * N - p;
}
Cout << ans << ’
```

’ ;

}

}

Complexity : **O(T * N / S)**

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution

Tester’s solution