DWITE Online Computer Programming Contest, February 2011, Problem 4

Over the years, many word games have been invented. However, most of them involve actually knowing the definitions of these words, and this can get kind of frustrating. So you decided to create a word game that doesn't involve knowing what words actually mean:

• You start out with a word.
• If there is a run of length 2 or more of some letter, you can remove the whole run from the word altogether (e.g. In the word GREEN, you can remove the two E's to get GRN).
• You keep removing runs of the same letters like above until you can't find any such runs.
• If the word is now empty, then you call the word you started with 'solvable'. If what remains isn't empty, then the word you started with is 'unsolvable'.

You then decide to make a program to help determine whether certain given words are solvable or not.

The input will contain 5 test cases. Each test case is a single line with 5 words separated by a single space, where each of these words consist of up to ~150~ uppercase characters.

The output should contain 5 lines. Each line consists of some 5 letter combination of S or U, where the ~i^\text{th}~ letter is an S if the ~i^\text{th}~ word in the input was solvable, or a U if the ~i^\text{th}~ word in the input was unsolvable.

Note: there might be more than one solution to a particular word.

Explanation of the first test case: GREEN is clearly unsolvable, since after removing the E's you are left with the string GRN. As for ABBA, removing the B's yields AA. You can then remove the A's to get rid of the whole word (making it solvable). POST and LEMONADE aren't solvable either, as there aren't any runs to remove in the first place. ROAAAOR is solvable, as you can remove the A's to get ROOR, and then you can remove the O's to get RR, and finally you remove the R's to get rid of the whole word.

Sample Input

GREEN ABBA POST LEMONADE ROAAAOR

Sample Output

USUUS

Problem Resource: DWITE