Задача №115121. Старт олимпиады
Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.
Всего в олимпиаде участвуют \(n\) человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.
Несмотря на разное время начала, длительность тура для каждого участника составляет ровно \(t\) минут. Из-за этого некоторые участники заканчивают писать тур раньше остальных. Когда участник заканчивает писать тур, величина недовольства организацией олимпиады для этого участника равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.
Помогите организаторам олимпиады выяснить, чему равно суммарное недовольство всех участников олимпиады.
В первой строке вводится единственное целое число \(n\) (\(1 \le n \le 2 \cdot 10^9\)) — число участников олимпиады.
Во второй строке вводится единственное целое число \(x\) (\(1 \le x \le 2 \cdot 10^9\)) — интервал в минутах между временами начала тура для участников.
В третей строке вводится единственное целое число \(t\) (\(1 \le t \le 2 \cdot 10^9\)) — длительность тура.
В единственной строке выведите одно число — суммарное недовольство всех участников олимпиады.
В первом примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(5\). К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно \(2\).
Второй участник начнёт писать в момент времени \(2\) и закончит в момент времени \(7\). К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно \(2\).
Третий участник начнёт писать тур в момент времени \(4\) и закончит в момент времени \(9\). К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно \(1\).
Четвёртый участник начнёт писать тур в момент времени \(6\) и закончит в момент времени \(11\). В момент времени \(9\) уже никто не будет писать тур, поэтому недовольство четвёртого будет равно \(0\).
Таким образом, суммарное недовольство всех участников будет равно \(2+2+1+0=5\).
Во втором примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(2\). К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени \(2\). Поэтому недовольство первого участника будет равно \(2\).
Второй участник начнёт в момент времени \(1\) и закончит в момент времени \(3\). К этому моменту только третий участник будет всё ещё писать тур.
Таким образом, суммарное недовольство всех участников будет равно \(2+1=3\).
В данной задаче \(20\) тестов, помимо тестов из условия, каждый из них оценивается в \(5\) баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n, x, t \le 10\), наберут не менее \(25\) баллов.
Решения, корректно работающие при \(n \le 1000\), наберут не менее \(50\) баллов.
Решения, корректно работающие при \(n \le 100\,000\), наберут не менее \(75\) баллов.
4 2 5
5
3 1 2
3
3 3 10
3