Задача №114560. Аквапарк
Ваш друг недавно построил большой аквапарк, и собирается открыть его для общественного доступа. Доступ в аквапарк будет проходить по сеансам длительностью \(a\) минут, то есть в начале сеанса аквапарк пускает всех желающих его посетить, и через \(a\) минут сеанс заканчивается и люди покидают аквапарк.
К сожалению, бассейны аквапарка могут загрязняться, поэтому если после окончания очередного сеанса прошло не менее \(m\) минут с момента начала предыдущей очистки бассейнов или первого запуска аквапарка, то бассейны надо очистить. Очистка бассейнов длится \(b\) минут, а после этого сеансы посещения аквапарка продолжаются. При этом изначально бассейны чистые, и в начале аквапарк готов принимать сеансы без предварительной очистки. Во время сеанса очистка бассейнов также не производится.
Вашему другу стало интересно, какое максимальное количество сеансов он сможет провести за \(n\) минут, если будет очищать бассейны сразу после конца сеанса, во время которого произошло их загрязнение.
В первой строке вводится целое число \(n\) (\(1 \le n \le 10^{18}\)) — общее время работы аквапарка.
Во второй строке вводится целое число \(m\) (\(1 \le m \le 10^{18}\)) — время от предыдущей очистки, через которое нельзя запускать новые сеансы, не очистив бассейнов.
В третей строке вводится целое число \(a\) (\(1 \le a \le m\)) — продолжительность сеанса аквапарка.
В четвёртой строке вводится целое число \(b\) (\(0 \le b < m\)) — продолжительность очистки бассейнов.
В единственной строке выведите максимальное число сеансов, которые могли бы быть организованы за \(n\) минут работы аквапарка.
В первом примере из условия первый сеанс идёт первые \(2\) минуты. Далее, так как с запуска прошло \(2\) минуты, то второй сеанс идёт на \(3\) и \(4\) минутах работы аквапарка. Таким образом после конца второго сеанса пройдёт \(4\) минуты с момента запуска аквапарка, поэтому на \(5\) и \(6\) минутах работы аквапарка пройдёт третий сеанс. После окончания третьего сеанса с начала работы пройдёт \(6\) минут, то есть с момента запуска аквапарка прошло хотя-бы \(m = 5\) минут, и значит надо очистить бассейны. Таким образом очистка будет происходить на \(7\), \(8\) и \(9\) минутах работы аквапарка. После этого останется лишь одна минута, за которую невозможно провести сеанс.
Во втором примере из условия первые \(3\) сеанса будут проходить на \(1\), \(2\) и \(3\) минутах. Потом пройдёт \(3\) минуты с момента запуска аквапарка, поэтому на минутах \(4\) и \(5\) будет очистка бассейнов, а на минуте \(6\) будет четвёртый сеанс. После этого пройдёт \(3\) минуты с начала предыдущей очистки бассейнов и значит на минутах \(7\) и \(8\) будет очередная очистка бассейнов. Далее на минуте \(9\) будет пятый сеанс, после него бассейны очистится и подготовится к следующему сеансу не успеют.
В данной задаче \(25\) тестов, помимо тестов из условия, каждый из них оценивается в \(4\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n, m, a, b \leq 10\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(n, m, a, b \leq 10^6\), наберут не менее \(40\) баллов.
Решения, корректно работающие при \(b = 0\), наберут не менее \(20\) баллов.
10 5 2 3
3
10 3 1 2
5
8 7 3 5
2