Виготовлення паркану#3102

Виготовлення паркану

3 секунди

64 мегабайти

Складна

Місто Хака добре відоме своїми заторами на дорогах. Це призвело до появи багатьох укладачів задач, адже люди часто вигадують нові задачі з програмування, чекаючи у заторі. Більшість широких доріг у Хаці мають паркани вздовж роздільника, і ці паркани зазвичай роблять із перфорованих сталевих листів (як показано на лівому малюнку).

У цій задачі ми розглядатимемо процес виготовлення певного типу перфорованої сталевої смуги, і вам необхідно розв'язати задачу, пов'язану з цим процесом.

Кожна прямокутна сталева смуга має два круглі отвори у кожному ряду. Отвори в одному ряду розташовані на відстані $2 d$ одиниць один від одного. Отвори у сусідніх рядах (тобто у тій самій колонці) також розташовані на відстані $2 d$ . Кожен отвір знаходиться на відстані $d$ від найближчого краю. Усі отвори мають радіус $r$ . Тому ширина кожної смуги становить $(4 d + 4 r)$ (4d + 4r), а початкова довжина смуги — $S$ . Приклад такої смуги з отворами зображено на правому малюнку. Отвори свердлять лише у випадку, якщо їх можна вирізати за наведеними правилами. Круглі сталеві листи, отримані з отворів, та невикористана частина смуги (наприклад, частина під червоною пунктирною лінією на правому малюнку) переплавляються для створення нової сталевої смуги шириною $(4 d + 4 r)$ (4d + 4r). Далі отвори вирізають у новій смузі згідно з тими ж правилами. Процес повторюється, поки новостворена смуга не стане настільки малою, що неможливо створити два отвори в одному ряду при вказаних обмеженнях.

Нехай $C (d, r, S)$ C(d, r, S) позначає загальну кількість отриманих отворів. Дано $r_{min}$ r_{min} (мінімальний можливий радіус отвору), $r_{ma x}$ r_{max} (максимальний можливий радіус отвору), $d_{min}$ d_{min} (мінімально допустима відстань), $d_{ma x}$ d_{max} (максимально допустима відстань) та $S$ . Вам потрібно знайти загальну кількість отриманих отворів.

Вважайте, що всі значення $d$ та $r$ — цілі числа. Початкова та будь-які наступні смуги мають однакову і рівномірну товщину по всій площі. Ваш розв'язок має бути достатньо ефективним для заданих обмежень.

Вхідні дані

Вхідний файл містить до $1000$ тестових випадків. Кожен тестовий випадок задано у єдиному рядку, який містить п'ять цілих чисел:

$r_{min}$ r_{min} $(5000 \leq r_{min} \leq 10000)$ (5000 \leq r_{min} \leq 10\,000), $r_{ma x}$ r_{max} $(0 \leq r_{ma x} - r_{min} \leq 1000)$ (0 \leq r_{max} - r_{min} \leq 1\,000), $d_{min}$ d_{min} $(1 \leq d_{min} \leq 21)$ (1 \leq d_{min} \leq 21), $d_{ma x}$ d_{max} $(0 \leq d_{ma x} - d_{min} \leq 100)$ (0 \leq d_{max} - d_{min} \leq 100), $S$ $(1000000 \leq S \leq 2000000000)$ (1\,000\,000 \leq S \leq 2\,000\,000\,000).

Вхід завершується рядком з п'яти нулів. Цей рядок обробляти не потрібно.

Вихідні дані

Для кожного рядка вхідних даних виведіть єдине ціле число — загальну кількість отворів, сумовану для всіх $d$ та $r$ у заданих діапазонах. Значення поміститься у 64-бітне знакове ціле число. Відповіді з відносною похибкою, що не перевищує $1 0^{- 7} %$ 10^{-7}\%, приймаються.

Приклади

Приклад 1