Перемешать
Мой офис находится довольно далеко от дома, и каждый день я добираюсь туда на автобусе. Это занимает много времени, и из-за пробок продолжительность поездки до офиса непостоянна. Чтобы максимально эффективно использовать это время, я всегда беру с собой музыкальный плеер.
У моего музыкального плеера есть режим «перемешивания». В этом режиме плеер случайным образом выбирает трек, который еще не был проигран в этой сессии, и начинает его воспроизведение. Он будет продолжать это делать до тех пор, пока я не остановлю воспроизведение или пока не будут проиграны все треки в этой сессии. Для целей этой задачи можно предположить, что все треки имеют одинаковую продолжительность. Чтобы выбрать случайный трек, плеер ведет список уже проигранных треков. То есть, если я сейчас слушаю один трек, то в следующей сессии перемешивания этот трек будет отмечен как проигранный. Чтобы выбрать случайный трек, плеер всегда использует такую стратегию, что выбор старого трека (уже прослушанного) в два раза более вероятен, чем нового трека (не прослушанного).
Я еду в офис утром и возвращаюсь домой вечером. Это занимает как минимум p минут и как максимум q минут. Время в пути всегда будет целым числом. Можно предположить, что все времена в пути равновероятны (то есть, если p = 2 и q = 4, и если P(t) — вероятность добраться до офиса за t минут, то P(2) = P(3) = P(4)). Если все треки длятся 1 минуту, сколько дней в среднем потребуется, чтобы прослушать все песни?
Входные данные
Первая строка ввода содержит целое число T(≤ 10053), количество тестов.
Каждый тест содержит 5 целых чисел, N (1 ≤ N ≤ 75), p_1, q_1, p_2, q_2 (0 ≤ p_1, q_1, p_2, q_2 ≤ 30, p_1 ≤ q_1, p_2 ≤ q_2), где N — количество песен, p_1, q_1 — минимальное и максимальное количество песен, прослушанных днем, и p_2, q_2 — минимальное и максимальное количество песен ночью.
Выходные данные
Для каждого теста выведите номер теста, за которым следует ожидаемое количество дней, необходимых для прослушивания всех песен. Если прослушать все песни невозможно, выведите "IMPOSSIBLE". Ошибки менее 10^{-6} будут допускаться.
Описание примера 1:
Каждый день я буду слушать либо 1 песню, либо ни одной. Вероятность прослушивания 1 песни равна
Вероятность не прослушать ни одной песни равна
Таким образом, вероятность прослушивания песни в первый день =
Вероятность прослушивания песни на второй день =
Вероятность прослушивания песни на второй день =
И так далее. Таким образом, ожидаемое количество дней будет:
Бесконечная сумма оценивается как , и, следовательно, ожидаемые дни =