1548. Diagonal

The number of diagonals of an n-gon is not less than N. What is the minimum possible value of n?

Input. Contains less than 1001 lines. Each line contains a positive integer N (N £ 10¹⁵) that indicates the minimum possible number of diagonals. Input is terminated by a line with one 0 that should not be processed.

Output. For each test case produce one line that contains serial number and the minimum possible value for n (number of sides).

Sample input	Sample output
10 100 1000 0	Case 1: 7 Case 2: 16 Case 3: 47

SOLUTION

mathematics

Algorithm analysis

Each point of the polygon is connected by segments with n – 1 other points. These line segments form 2 sides and n – 3 diagonals. Since there are n points in the polygon, and n – 3 diagonals get out from each point, the number of diagonals of a convex n - gon is n * (n – 3) / 2 (each diagonal is counted twice).

If n * (n – 3) / 2 = N, then the value of n can be found from the quadratic equation

n² – 3 * n – 2 * N = 0

The positive root of the equation is

It remains to round up the computed value. Since N £ 10¹⁵, the calculations should be performed using long long data type.

Example

Consider the second test case. For N = 100 we have

n = = 16

Algorithm realization

Read the input data while N > 0, calculate the result using the formula and print it with the test number.

int cs = 1;

while(scanf("%lld",&n), n > 0)

{

res = int(ceil((3 + sqrtl(9.0 + 8*n)) / 2));

printf("Case %d: %d\n",cs,res);

cs++;

}

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n, cs = 1;

while((n = con.nextLong()) > 0)

{

long res = (int)(Math.ceil((3 + Math.sqrt(9 + 8*n))/2));

System.out.println("Case " + cs + ": " + res);

cs++;

}

}

}