1160 - Problem K: Bridged Marble Rings

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 18

Solved: 5

Description

26 marbles—half yellow and half gray—are distributed between two circles of 13 marbles each. The marbles in each circle can be freely rotated clockwise or counterclockwise. The upper and lower circles are bridged by a smaller circle, which rotates—in the plane of the board—180 degrees, effectively exchanging the three bottommost marbles of the upper circle with the three uppermost marbles of the lower one. The goal is to get all gray marbles to the upper circle and all yellow marbles to the lower one while minimizing the number of times the bridging circle is rotated.

Input

The input is a series of lines, where each line describes an initial board configuration.
Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one.
The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13 g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

Output

For each input case, you should print the minimum number of bridge rotations on a single line.

sample input

gggggggggggggyyyyyyyyyyyyy 
yyyyyggggggggyyyygggggyyyy 
gyyygyggyyygyyggyyggggyygg 
ygygygygygygygygygygygygyg

sample output

hint

source