Только что закончилос on-line программерское соревнование. Решил 2 задачи из 9 что вообщем не плохо. Я где то на 70-м месте из 500…. Первые места заняли сборные команды.
Третью задачу решал почти 2 часа и придумал как мне казалось иделаьный бстрый алгоритм, но ни хрена … не укладываюсь в отведенные 2 секунды.
Есть S рыбаков, они поймали какое то количество рыбы и легли спать. Проснулся первый рыбак, разделил всю рыбу на S частей, забрал свою часть и у него осталось лишние M рыб. Их он выкинул и ушел. Затем проснулся следующий рыбак, разделил оставшиеся на S частей и у него тоже осталось ровно M рыб. И так далее, до последнего рыбака. Утром они вернулись и обнаружили что число оставшейся рыбы можно разделить на всех без остатка.
Дан интервал 0 <= L, H, <= 10^8. Необходимо найти число возможных количеств рыбы которой они поймали из этого интервала.
Тестовый пример (Первое число — общее число тестов):
На каждой строчке дано 4 числа: S — число рыбаков, M — число оставшейся рыбы после каждого разделения, L, U — границы (включительно) интервала в котором необходимо искать ответ
|
Sample Input |
Output for Sample Input |
|
3 |
Case 1: 1 |
Иллюстрация для первого примера:
|
Рыбак # |
Общее число оставшейся рыбы |
Сколько забрал |
Сколько выкинул |
Оставшееся |
|
1 |
50 |
16 |
2 |
32 |
|
2 |
32 |
10 |
2 |
20 |
|
3 |
20 |
6 |
2 |
12 |
В первом тестовом примере дано: 3 рыбака и 2 рыбы которые выкидывал каждый из рыбаков. Интервал [49, 50].
Если проверить то видно что данному сценарию удовлетворяет только число 50 из этого интервала. Следовательно ответ 1.
Помочь с этой задачкой надо?
Уже не надо, но можешь решить. Или хотя бы алгоритм быстрый написать тут =)
Эту задачу поместили в общую базу. Моя прога которую я написал работет 6 секнуд и что характерно Accepted. А во время соревнования лимит был 3 секунды. =(
З.Ы. У задачи есть аналитическое решение. Т.к. есть пиплы решившие её за 0.000 секунд и почти не юзая память …