A hard problem again (at least with me -.-)
PSW is a interesting game. When starting a game, you: a have 5 integers,b,x,y,m. Each step, you can use one of three below operations to convert the pair (a,b) to the pair (x,y). Each operations is one of the following:
1. Addition (P). It can occur if a + b <= m and convert (a,b) to (a+b,b).
2. Subtraction (S). It can occur if a>b and convert (a,b) to (a-b,b).
3. Swap (W). Convert (a,b) to (b,a).
A way to convert the pair (a,b) to the pair (x,y) is described by a string that consists of 3 characters: ‘P’, ‘S’ and ‘W’. For example, converting (3,10) to (3,1) can be done in the following steps: (3,10) -> (10,3) -> (7,3) -> (4,3) ->(1,3) -> (3,1) and the way to play is expressed by string WSSSW.
Described string can compress by replacing all of repeatedly consecutively characters by repeated character and number of iterations (in the case that repeating a character is greater than 1 time) . For example, the string WSSSW can compress to WS3W.
It is guaranteed that string “PP”, “SS”, “WW” don’t appear in the compressed string, the length of answer string is less than or equal to 10000 and the answer is always exist.
Condition: a,b,x,y <= m and m <= 10^9.
Giving 5 numbers a, b, x, y, m, your task is to find the string that describes the way to play.
Example:
INPUT:
3 10 3 1 100
OUTPUT:
WS3W
INPUT:
1 1 1000 1 1000
OUTPUT:
P999
Any ideal to solve it?
Thanks in advance.