The pandemic has spread to all countries of the world, and Berland is no exception. Even at the All-Berland Olympiad in Computer Science, antiviral measures were introduced.
In total, n people participate in the Olympiad, and in order to comply with all the instructions of the management, the Olympiad jury decided to invite participants to the tour one at a time with an interval of x minutes. Thus, the first participant will start the tour at time 0, the second participant will start the tour at time x, the third — at time 2x and so on.
Despite the different start times, the duration of the tour for each participant is exactly t
minutes. Because of this, some participants finish writing the tour before the rest. When a participant finishes writing a tour, the amount of dissatisfaction with the organization of the Olympiad for this participant is equal to the number of other participants who are currently still writing or just starting to write a tour, but have not finished it yet.
Help the organizers of the Olympiad to find out what the total dissatisfaction of all participants of the Olympiad is equal to.
Input:
A single integer n is entered in the first line 1<=n<=2 * 10^9 — the number of participants of the Olympiad.
A single integer x is entered in the second line 1<=x<=2 * 10^9 — the interval in minutes between the start times of the tour for participants.
In the third line, a single integer t is entered 1<=t<=2 * 10^9 — duration of the tour.
Output:
In a single line, print one number — the total dissatisfaction of all participants of the Olympiad.
Examples:
Input:
4
2
5
Output:
5
Input:
3
1
2
Output:
3
Input:
3
3
10
Output:
3
Note
In the first example , the first participant will start writing the tour at time 0 and finish at time 5. By this time, the second and third participants will already start writing the tour, so the dissatisfaction of the first participant will be equal to 2.
The second participant will start writing at time 2 and finish at time 7. By this point, the third and fourth participants will already start writing the tour, so the dissatisfaction of the second will be equal to 2.
The third participant will start writing the tour at time 4 and finish at time 9. By this time, the fourth participant will already start writing the tour, so the dissatisfaction of the third will be equal to 1.
The fourth participant will start writing the tour at time 6 and finish at time 11. At time 9 no one will write a tour anymore, so the dissatisfaction of the fourth will be equal to 0.
Thus, the total dissatisfaction of all participants will be equal to 2+2+1+0=5.
In the second example , the first participant will start writing the tour at time 0 and finish at time 2. By this point, the second participant will already be writing the tour, and the third participant will just start at time 2. Therefore , the dissatisfaction of the first participant will be equal to 2.
The second participant will start at time 1and finish at time 3. By this point, only the third participant will still be writing the tour.
Thus, the total dissatisfaction of all participants will be equal to 2+1=3.
def qwerty(n, x, t):
time_finish_before_start = t + x * (n - 1)
time_start_before_finish = t + x * (n - 2)
dissatisfaction_finish_before_start = min(n - 1, time_finish_before_start // x)
dissatisfaction_start_before_finish = max(0, n - 2 - dissatisfaction_finish_before_start)
total_dissatisfaction = dissatisfaction_finish_before_start * dissatisfaction_start_before_finish
return total_dissatisfactionimport codewars_test as test
# TODO Write tests
import solution # or from solution import example
# test.assert_equals(actual, expected, [optional] message)
@test.describe("Example")
def test_group():
@test.it("test case")
def test_case():
test.assert_equals(1 + 1, 2)