TaroFillingAStringDiv1

SRM 650 · 2015-01-29 · by Witaliy

SRM 650 · 2015-01-29 · by Witaliy · Brute Force

Show categories

Class Name: TaroFillingAStringDiv1

Return Type: int

Method Name: getNumber

Arg Types: (int, vector<int>, string)

Problem Statement

Cat Taro likes strings. He is currently constructing a string S of length N. Each character of S will be either 'A' or 'B'. Taro has already chosen some of the characters. You are given these choices as a int[] position and a String value. For each valid i, the character at the 1-based index position[i] in S is the character value[i].

To Taro, the ugliness of a string is the number of pairs of equal consecutive characters. For example, the ugliness of "ABABAABBB" is 3: there is one pair "AA" and two (overlapping) pairs "BB".

Taro now wants to finish S by filling in the remaining characters. His goal is to create a string with the smallest possible ugliness. Let X be the number of possible strings Taro may produce. Return the value (X modulo 1,000,000,007).

Constraints

N will be between 1 and 1,000,000,000, inclusive.
position will contian between 1 and 50 elements, inclusive.
value and position will contain the same number of elements.
Each element of position will be between 1 and N, inclusive.
All elements of position will be distinct.
value will consist only of characters 'A' and 'B'.

Examples

3
{1, 3}
"AB"
Returns: 2

Currently, Taro's string looks as follows: A_B. He can either produce the string AAB or the string ABB. Both have the same ugliness.

4
{2, 1, 3, 4}
"ABBA"
Returns: 1

All characters of S have already been chosen.

3
{2, 3}
"AB"
Returns: 1

2
{1, 2}
"AB"
Returns: 1

6
{5, 4, 3, 2, 1}
"ABAAB"
Returns: 1

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

Coding Area

Language: C++17 · define a public class TaroFillingAStringDiv1 with a public method int getNumber(int N, vector<int> position, string value) · 110 test cases · 2 s / 256 MB per case