ColorfulRoad
SRM 596 · 2013-06-25 · by ir5
Problem Statement
There is a one-dimensional road. The road is separated into N consecutive parts. The parts are numbered 0 through N-1, in order. Ciel is going to walk from part 0 to part N-1.
Ciel also noticed that each part of the road has a color: either red, green, or blue. Part 0 is red.
Ciel is going to perform a sequence of steps. Each step must lead in the positive direction. That is, if her current part is i, the next step will take her to one of the parts i+1 through N-1, inclusive. Her steps can be arbitrarily long. However, longer steps are harder: a step of length j costs j*j energy.
Additionally, Ciel wants to step on colors in a specific order: red, green, blue, red, green, blue, ... That is, she starts on the red part 0, makes a step to a green part, from there to a blue part, and so on, always repeating red, green, and blue in a cycle. Note that the final part N-1 also has some color and thus Ciel must reach it in a corresponding step.
You are given a
Constraints
- road will contain between 2 and 15 characters, inclusive.
- Each character of road will be either 'R' or 'G' or 'B'.
- The first character of road will be 'R'.
"RGGGB" Returns: 8
The optimum solution is to step part 0 -> part 2 -> part 4. The total cost is 2*2 + 2*2 = 8.
"RGBRGBRGB" Returns: 8
The optimum solution is to make steps of length 1. It costs 1*1 = 1 per each step, so the total cost is 8.
"RBBGGGRR" Returns: -1
It is impossible to reach the destination.
"RBRRBGGGBBBBR" Returns: 50
"RG" Returns: 1
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ColorfulRoad with a public method int getMin(string road) · 81 test cases · 2 s / 256 MB per case