VPL2_AC - Primos Quest

no tags 

Primo is playing Guitar Hero, but he has been playing it for quite long, and his hand is a little tired. He knows that for every change between colors his energy goes down. The colors of the guitar are ordered like this: Green, Red, Yellow, Blue and Orange. The energy to change from playing a color A, to a color B, is the absolute difference of the distance between them, by example, changing from Red to Yellow, costs 1 unit of energy, and changing from Blue to Green costs 3 units of energy. Primo knows that he has exactly C units of energy left, and he also know the colors of the notes from a random song. Help him find out the maximum number of notes in a row that he can play on this song.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

For each test case you will have a single line containing an integer C, representing the energy left of Primo, and a string S, representing the colors and the order of the notes from the song. Each character in S will be ’G’ for Green, ’R’ for Red, ’Y’ for Yellow, ’B’ for Blue or ’O’ for Orange.

Output

For each input case you must print Scenario #i: where i is the number of the test case (starting at one), and then the answer to the problem.

Sample

Input
3
0 OORRBYYYGG
1 RRORGRRRBOY
3 RRRORORRRR

Output
Scenario #1: 3
Scenario #2: 4
Scenario #3: 5

Constraints

Constraints - 40%

1 ≤ T ≤ 100

0 ≤ C, |S| ≤ 1000

Constraints - 60%

1 ≤ T ≤ 100

0 ≤ C, |S| ≤ 1000000


hide comments
Gaurang Singhal: 2015-01-04 11:35:02

Cluster Pyramid has been depricated so please transfer it to Cube so that we can submit our codes.

Aditya Joshi: 2014-10-03 09:05:45

Good problem!

Arpit Uppal: 2013-12-11 17:17:25

2nd test case is the most important case ;)

rahul kumar singh: 2013-08-02 13:41:24

@Venezuelan Programming League how can string size be equal to 0?

devil: 2013-07-11 17:42:45

even O(|S|) giving tle?

Vijay: 2013-07-11 08:10:55

It is not necessary to spend all C units of energy to get the maximum number of notes!

Vipul Pandey: 2013-07-04 19:44:29

good problem!

technophyle: 2013-06-29 15:15:08

After this problem try problem ALIEN

technophyle: 2013-06-29 15:15:08

@author: isn't the first test case invalid since on contraints it is mentioned that 1 <= C <= 1000000.

But in test case #1 C = 0. Please Update Test Cases appropriately.

Last edit: 2013-06-28 13:55:37
Venezuelan Programming League: 2013-06-29 15:15:08

I think the cases are simple enough, however, i will explain it.

1st: As you have no energy left, you will play the same keys, so you must select the best continuous combo, in the case of 'OORRBYYYGG' it should be 'YYY'

In the third case 'RRRORORRRR' you have 3 energy left, so you can play 'RRRO', 'OR' and 'ORRRR' (this three substrings are wasting the whole three energy points), however 'ORRRR' is larger and then its the answer, please note that 'RRRR' is a valid substring, but it's not optimal.


Added by:Venezuelan Programming League
Date:2013-06-22
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64