AIOC Banner

Problem: Halloween

Want to try solving this problem? You can submit your code online if you log in or register.


Halloween

Input File: hallin.txt
Output File: hallout.txt
Time Limit: 0.333 second

October 31 is approaching. As Director of Operations for trick-or-treating in your suburb, it is your job to determine precisely which children should visit which houses dressed in scary costumes demanding free food.

Intelligence from your market research team indicates that adults in your neighbourhood tend to behave as follows. When the first child knocks on the door, (s)he gives them one lolly. When the second child knocks on the door, (s)he gives them two lollies. The third child is given three lollies and so on, giving more lollies to each successive child in the hope that the lollies will run out faster so (s)he can bolt the door and go to bed.

Your surveillance team has reported precisely how many lollies each adult has purchased over the last week. Your task is to determine how many children to send to each house.

Input

Each input file will contain a single integer n representing the number of lollies a particular adult has. You are guaranteed that 0 <= n <= 10,000.

Output

The output file must contain a single line representing the first dissatisfied child (the child who doesn't receive as many lollies as they expect).

Example

Say the input file indicates an adult with 12 lollies. In this case the first child receives 1 lolly, the second child receives 2, the third receives 3 and the fourth receives 4. At this point the adult has given away 1+2+3+4 = 10 lollies.

The fifth child should receive 5 lollies, but the adult has only 2 lollies remaining. Thus the fifth child will not receive as many lollies as they expect.

Sample Input

12

Sample Output

5

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 19 August 2019, 11:42am AEST