eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Shuffle

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

My office is quite far from my home. Every day, I go there by bus. That takes a lot of time. More over, due to traffic jams, the time to reach my office is not fixed. To make the best use of this time, I carry my music player all the time.

My music player has a ‘shuffle’ mode. In that mode, the music player selects a track randomly that has not been played in that session, and starts playing. It will continue doing so, until, I have stopped playing, or it has played all tracks in that session. For the purpose of this problem, you can assume that all tracks are of equal duration. To select randomly, the player keeps list of the tracks already played. That is, if I listen to one track now, from next shuffle session, that track will be marked as played. To select a random track, the player always use such strategy that, selecting an old track (Already listened) is twice more probable than a new track (Not listened).

I go to my office in the morning and return home at night. It takes at least p minutes and at most q minutes to reach my office. The time required will always be an integer. You can assume that all travel times are equiprobable (that is, if p = 2 and q = 4, and if P(t) is the probability to reach office in t minutes, then P(2) = P(3) = P(4)). If all tracks are of 1 minute, how many days on average are required to listen to all the songs?

Входные данные

First line of input contains an integer T(≤ 10053), the number of test cases.

Each test case contains 5 integers, N (1N75), p_1, q_1, p_2, q_2 (0p_1, q_1, p_2, q_230, p_1q_1, p_2q_2), where N is the number of songs, p_1, q_1 are the minimum and maximum number of songs listened during day, andp_2, q_2 are the minimum and maximum number of songs during night.

Выходные данные

For each test case, output the test case, followed by the expected number of days required to listen to all songs. If it’s not possible to listen to all songs, output "IMPOSSIBLE". Errors less than 10^{-6} will be tolerated.

Description of sample case 1:

Each day, I will listen to either 1 song, or no song. Probability of listening to 1 song is

Probability of not listening to any song is

So, probability of listening the song on the first day =

Probability of listening the song on the second day =

Probability of listening the song on the second day =

And so on. So, the expected number of days will be:

The infinite sum evaluates to , and thus, expected days =

Пример

Входные данные #1
5
1 0 1 0 1
1 0 1 0 0
1 0 0 0 1
2 1 1 0 0
3 0 1 0 2
Выходные данные #1
Case 1: 1.3333
Case 2: 2.0000
Case 3: 2.0000
Case 4: 4.0000
Case 5: 4.9630
Источник ACM-ICPC Thailand National Programming Contest 2010, Prince of Songkla University Phuket Campus 24 August 2010