Skyscraper MinatoHarukas
InterviewTime limit2sMemory limit512 MB
For each budget b, find the longest run of consecutive positive integers summing to b and print its first floor and length.
- Level
Medium6 of 10
- Topics
- Math, Two pointers, Number theory, Implementation
- Solved
- No attempts yet
Problem
Mr. Port plans to start a new business renting one or more floors of the new skyscraper MinatoHarukas, which has one billion floors. He wants to rent as many vertically adjacent floors as possible, because he wants to show advertisements on as many vertically adjacent windows as possible. The rent for one floor is proportional to the floor number, that is, the rent per month for the n-th floor is n times that of the first floor. Here, the ground floor is called the first floor in the American style, and basement floors are out of consideration for the renting. To help Mr. Port, write a program that computes the vertically adjacent floors satisfying his requirement and whose total rental cost per month is exactly equal to his budget.
For example, when his budget is 15 units, with one unit being the rent of the first floor, there are four possible rent plans, 1+2+3+4+5, 4+5+6, 7+8, and 15. For all of them, the sums are equal to 15. In this example, the plan with the maximal number of floors is 1+2+3+4+5, that is, the rent from the first floor to the fifth floor.
Input
The input consists of multiple datasets, each in the following format.
b
A dataset consists of one line, the budget of Mr. Port b as multiples of the rent of the first floor. b is a positive integer satisfying 1 < b < 10^9.
The end of the input is indicated by a line containing a zero. The number of datasets does not exceed 1000.
Output
For each dataset, output a single line containing two positive integers representing the plan with the maximal number of vertically adjacent floors whose rent price is exactly equal to the budget of Mr. Port. The first should be the lowest floor number and the second should be the number of floors.