Codeforces Round 727 (Div. 2) |
---|
Закончено |
В некоторой олимпиаде участвует $$$n$$$ человек, причем они начинают олимпиаду с интервалом в $$$x$$$ минут. Таким образом первый участник начнёт тур в момент времени $$$0$$$, второй участник начнёт тур в момент времени $$$x$$$, третий — в момент времени $$$2 \cdot x$$$ и так далее.
Длительность тура для каждого участника составляет ровно $$$t$$$ минут, то есть первый участник закончит в момент времени $$$t$$$, второй — в момент времени $$$t + x$$$, и так далее. Когда участник заканчивает писать тур, величина его недовольства равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.
Определите, чему равно суммарное недовольство всех участников олимпиады.
В первой строке вводится единственное число $$$k$$$ ($$$1 \le k \le 1000$$$) — количество наборов входных данных.
Каждая из следующих $$$k$$$ строк содержит по три целых числа $$$n$$$, $$$x$$$, $$$t$$$ ($$$1 \le n, x, t \le 2 \cdot 10^9$$$) — число участников олимпиады, интервал в минутах между временами начала тура для участников и длительность тура.
Выведите $$$k$$$ строк, в $$$i$$$-й из них выведите суммарное недовольство всех участников олимпиады для $$$i$$$-го набора входных данных.
4 4 2 5 3 1 2 3 3 10 2000000000 1 2000000000
5 3 3 1999999999000000000
В первом наборе входных данных первый участник начнёт писать тур в момент времени $$$0$$$ и закончит в момент времени $$$5$$$. К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно $$$2$$$.
Второй участник начнёт писать в момент времени $$$2$$$ и закончит в момент времени $$$7$$$. К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно $$$2$$$.
Третий участник начнёт писать тур в момент времени $$$4$$$ и закончит в момент времени $$$9$$$. К этому времени четвёртый уже начнёт писать тур, поэтому недовольство третьего будет равно $$$1$$$.
Четвёртый участник начнёт писать тур в момент времени $$$6$$$ и закончит в момент времени $$$11$$$. В момент времени $$$11$$$ уже никто не будет писать тур, поэтому недовольство четвёртого будет равно $$$0$$$.
Во втором наборе входных данных первый участник начнёт писать тур в момент времени $$$0$$$ и закончит в момент времени $$$2$$$. К этому моменту второй уже будет писать тур, а третий как раз начнёт в момент времени $$$2$$$. Поэтому недовольство первого участника будет равно $$$2$$$.
Второй начнёт в момент времени $$$1$$$ и закончит в момент времени $$$3$$$. К этому моменту только третий будет всё ещё писать тур.
Название |
---|