Diagonal (Анализа на решението)

Each vertex of a convex polygon is connected by segments to the remaining n - 1 vertices. Among these, two segments form the sides of the polygon, and the remaining n - 3 are diagonals. Since there are $n$ vertices in total, and each vertex is connected to n - 3 diagonals, the total number of diagonals in a convex $n$-gon is given by:

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

The positive root of this equation is

We round this value up to the nearest integer. Since N \le 10^{15}, all computations should be performed using the long long data type.

Example

Let's consider the second test case. For N = 100 we get:

Algorithm implementation

Store the current test number in the variable $cs$.

int cs = 1;

Read the input data as long as the value of $N$ is greater than zero.

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

For each value of $N$, compute the result using the formula and print it along with the test number.

  res = int(ceil((3 + sqrtl(9.0 + 8*n)) / 2));
  printf("Case %d: %d\n",cs,res);
  cs++;
}

Java implementation

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++;
    }
  }
}