Задача №112749. Вырубка леса
Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на
месте которого должно быть кукурузное поле. В лесу растут \(X\) деревьев.
Дмитрий срубает по A деревьев в день, но каждый \(K\)-й день он отдыхает и не срубает
ни одного дерева. Таким образом, Дмитрий отдыхает в \(K\)-й, 2\(K\)-й, 3\(K\)-й день, и т.д.
Федор срубает по B деревьев в день, но каждый \(M\)-й день он отдыхает и не срубает ни
одного дерева. Таким образом, Федор отдыхает в \(M\)-й, 2\(M\)-й, 3\(M\)-й день, и т.д.
Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не
отдыхает, они срубают \(A\) + \(B\) деревьев, в дни, когда отдыхает только Федор — \(A\) деревьев, а в
дни, когда отдыхает только Дмитрий — \(B\) деревьев. В дни, когда оба лесоруба отдыхают, ни
одно дерево не срубается.
Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он
сможет засеять кукурузное поле.
Требуется написать программу, которая по заданным целым числам \(A\), \(K\), \(B\), \(M\) и \(X\)
определяет, за сколько дней все деревья в лесу будут вырублены.
Входной файл содержит пять целых чисел, разделенных пробелами: \(A\), \(K\), \(B\), \(M\) и \(X\) (1 ≤ \(A\), \(B\) ≤ \(10^9\) , 2 ≤ \(K\), \(M\) ≤ 1018, 1 ≤ \(X\) ≤ 1018).
Выходной файл должен содержать одно целое число — искомое количество дней.
В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим
образом:
* 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
* 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10
деревьев;
* 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
* 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
* 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20
деревьев;
* 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
* 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого
все 25 деревьев срублены.
Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но
решение принимается на проверку только в том случае, если оно выводит правильный ответ
на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно
рассчитано на решение только каких-либо из подзадач 2 и 3
Подзадача 1 (32 балла)
1 ≤ \(X\) ≤ 1000, 1 ≤ \(A\), \(B\) ≤ 1000, 2 ≤ \(K\), \(M\) ≤ 1000
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (10 баллов)
1 ≤ \(X\) ≤ 1018
\(X\) < \(K\)
\(X\) < \(M\)
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ \(X\) ≤ 1018
Дополнительно к приведенным ограничениям выполняется условие \(K\) = \(M\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ \(X\) ≤ 1018, 1 ≤ \(A\), \(B\) ≤ \(10^9\), 2 ≤ \(K\), \(M\) ≤ 1018
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест
начисляются независимо.
2 4 3 3 25
7