Изготовление забора
Город Хака славится своими пробками, что вдохновило многих составителей задач на создание новых задач для программных конкурсов. В пробках у людей появляется время для размышлений, и они часто придумывают новые задачи. На большинстве широких дорог в Хаке вдоль разделителей установлены заборы, которые часто изготавливаются из перфорированных стальных листов (как показано на изображении слева).
В этой задаче мы обсудим процесс производства одного типа перфорированных стальных полос и предложим вам решить задачу, связанную с этим процессом.
Перфорированные стальные полосы в этой задаче имеют два круглых отверстия в каждом ряду. Расстояние между отверстиями в одном ряду составляет 2d, а между отверстиями в одном столбце — также 2d. Каждое отверстие находится на расстоянии d от ближайшей стороны полосы. Радиус всех отверстий равен r. Таким образом, ширина металлического листа/полосы составляет (4d+4r). Длина исходного листа равна S. Такой лист с отверстиями показан на изображении справа. Отверстия сверлятся только в том случае, если их можно вырезать в соответствии с указанными правилами. Круглые стальные листы, полученные из вырезанных отверстий, и часть листа, которая не используется (например, часть ниже красной пунктирной линии на изображении справа), переплавляются для создания нового стального листа/полосы шириной (4d+4r). Затем в новом листе вырезаются отверстия по тем же правилам. Этот процесс повторяется до тех пор, пока новый лист не станет настолько мал, что в нем невозможно будет создать два отверстия в одном ряду в соответствии с вышеупомянутыми ограничениями. Пусть C(d, r, S) обозначает общее количество созданных отверстий. Теперь, зная минимальное возможное значение r (r_min), максимальное возможное значение r (r_max), минимальное возможное значение d (d_min) и максимальное возможное значение d (d_max), вам нужно найти общее количество созданных отверстий.
Другими словами, вам нужно найти . Теперь вам должно быть ясно, что значения d и r всегда являются целыми числами. Ваш метод должен быть достаточно эффективным. Вы должны предположить, что начальная заданная полоса и полосы, созданные позже, имеют равную и равномерную толщину во всех местах.
Входные данные
Файл ввода содержит 1000 наборов входных данных. Входные данные для каждого набора представлены в одной строке. Каждая строка содержит пять целых чисел: r_min (5,000 ≤ r_min ≤ 10,000), r_{max }(0 ≤ r_max - r_min ≤ 1,000), d_min (1 ≤ d_min ≤ 21), d_max (0 ≤ d_max - d_min ≤ 100) и S (1,000,000 ≤ S ≤ 2,000,000,000). Теперь вам должно быть ясно, что значения r и d могут быть только целыми числами.
Ввод завершается строкой, содержащей пять нулей. Эта строка не должна обрабатываться.
Выходные данные
Для каждого набора/строки ввода выведите одну строку вывода. Эта строка содержит целое число, которое обозначает значение . Вы можете быть уверены, что значение этого целого числа легко поместится в 64-битное знаковое целое число. Ошибки, не превышающие 10^{-7 }%, будут игнорироваться.