Problem Description
There are many similarities between the human and the Navi cultures and lifestyles. For instance, their sports and boardgames bear similarities to different sports and games on Earth. But at the same time, there are significant differences (e.g., instead of water polo, they play air polo on their Banshees).There is also a version of Billiards, which is quite similar to our version, but with the difference that their Billiards table has a large circular hole right at the center (see figure). Of course, a person who hits the ball into that hole immediately loses.
Jake and Tsu’tey start a friendly game of Billiards which soon turns into a not-so-friendly game with possibly the leadership of the Omaticaya at stake. In each round, they take turns. At each turn, an impartial judge places the cue ball at one location on the table (call it point A) and another ball somewhere else (call it point B). The person whose turn it is, must hit the ball at point B from point A with minimum number of rebounds off the walls of the table (see figure).
Your goal is to help Jake win the game and retain his leadership (otherwise he will have to try to tame Toruk once again, and only so many times you can survive that). Given the input parameters, you are to find the minimum number of rebounds needed to get from point A to point B (or declare that it is not possible to do so). Assume the board is perfectly frictionless and the walls are infinitely elastic. So a ball hit at an angle 1 will rebound in the opposite direction at exactly the same angle.
Input
The Billiards table is a square with dimensions 100 by 100. Assume that the center of the table (and hence the center of the hole at the middle) is at (0, 0). You are given the x and y coordinates of the points A and B, and also the radius of the hole in the middle (r). The first line of the input file is the number of test cases. Each line contains 5 integers: Ax,Ay,Bx,By, r, where (Ax,Ay) are the coordinates of point A, and (Bx,By) are the coordinates of point B. The value r denotes the radius.
You can assume that neither point A nor point B are in the hole, and that r < 50.
Output
For each test case, you are to find the minimum number of rebounds needed to reach from point A to point B. If it is less than 10, output on a single line ”REBOUNDS” followed by the number of rebounds needed. If it is not possible to hit point B from point A in < 10 rebounds, output on a single line ”NOT POSSIBLE”.
Sample Input
2
16 -14 38 -27 13
21 44 -38 -17 38
Sample Output
REBOUNDS 2
NOT POSSIBLE
Problem Description
Ice-sugar gourd, “bing tang hu lu”, is a popular snack in Beijing of China. It is made of some fruits threaded by a stick. The complicated feeling will be like a both sour and sweet ice when you taste it. You are making your mouth water, aren’t you?
I have made a huge ice-sugar gourd by two kinds of fruit, hawthorn and tangerine, in no particular order. Since I want to share it with two of my friends, Felicia and his girl friend, I need to get an equal cut of the hawthorns and tangerines. How many times will I have to cut the stick so that each of my friends gets half the hawthorns and half the tangerines? Please notice that you can only cut the stick between two adjacent fruits, that you cannot cut a fruit in half as this fruit would be no good to eat.
Input
The input consists of multiply test cases. The first line of each test case contains an integer, n(1 <= n <= 100000), indicating the number of the fruits on the stick. The next line consists of a string with length n, which contains only ‘H’ (means hawthorn) and ‘T’ (means tangerine).
The last test case is followed by a single line containing one zero.
Output
Output the minimum number of times that you need to cut the stick or “-1” if you cannot get an equal cut. If there is a solution, please output that cuts on the next line, separated by one space. If you cut the stick after the i-th (indexed from 1) fruit, then you should output number i to indicate this cut. If there are more than one solution, please take the minimum number of the leftist cut. If there is still a tie, then take the second, and so on.
Sample Input
4
HHTT
4
HTHT
4
HHHT
0
Sample Output
2
1 3
1
2
-1