AnEasyProblem

TCO 2014 Celebrity Match · 2014-03-26 · by dreamoon

TCO 2014 Celebrity Match · 2014-03-26 · by dreamoon · Simple Math

Show categories

Class Name: AnEasyProblem

Return Type: int

Method Name: solve

Arg Types: (long long)

Problem Statement

NOTE: This problem statement contains subscripts/superscripts that may not display properly if viewed outside of the applet.

For positive integers h and r (1 &lt= r &lt= h) we define sequence F_h,r as {1, 2, 3, ..., h-1, h, h-1, h-2, ..., r+1, r}. Let S(F_h,r) be the the sum of all numbers in F_h,r and N(F_h,r) - the length of F_h,r.

For example, F_3,2 is {1, 2, 3, 2}, S(F_3,2) = 1 + 2 + 3 + 2 = 8, and N(F_3,2) = 4. F_5,5 is {1, 2, 3, 4, 5}, S(F_5,5) = 15, and N(F_5,5) = 5.

You are given a long sum. Return minimal possible N(F_i,j) such that S(F_i,j) = sum. If there is no such sequence F_i,j, return -1 instead.

Constraints

sum will be between 1 and 1,000,000,000,000(10^12).

Examples

6
Returns: 3

When h = r = 3, S(Fh,r) = 6 and N(Fh,r) = 3. There is no other h,r satisfing S(Fh,r) = 6. So you should return 3.

7
Returns: -1

100
Returns: 15

1000000000000
Returns: 1428571

999999911791
Returns: 1414213

Submissions are judged against all 40 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AnEasyProblem with a public method int solve(long long sum) · 40 test cases · 2 s / 256 MB per case