Діагональ#1548

Діагональ (Розбір)

Кожна вершина опуклого многокутника з'єднана відрізками з рештою $n - 1$ n - 1 вершин. Із них два відрізки утворюють сторони, а решта $n - 3$ n - 3 є діагоналями. Оскільки всього вершин $n$ , і з кожної виходить $n - 3$ n - 3 діагоналі, то загальна кількість діагоналей в опуклому $n$ -кутнику дорівнює $n \cdot (n - 3) /2$ n \cdot (n - 3) / 2 (оскільки кожна діагональ враховується двічі).

Якщо $n * (n - 3) /2 = N$ n * (n - 3) / 2 = N, то значення $n$ можна знайти з квадратного рівняння:

n^{2} - 3 \cdot n - 2 \cdot N = 0

n^2 - 3 \cdot n - 2 \cdot N = 0

Позитивний корінь цього рівняння дорівнює

n = \frac{3 + 9 + 8 N}{2}

n = {3 + \sqrt{9 + 8N} \over 2}

Залишається округлити це значення вгору до найближчого цілого. Оскільки $N \leq 1 0^{15}$ N \le 10^{15}, всі обчислення слід виконувати з використанням типу даних long long.

Приклад

Розглянемо другий тест. Для $N = 100$ N = 100 отримаємо

n = ⌈ \frac{3 + 9 + 8 \cdot 100}{2} ⌉ = 16

n = \left\lceil{3 + \sqrt{9 + 8 \cdot 100} \over 2}\right\rceil = 16

Реалізація алгоритму

Номер поточного тесту будемо зберігати в змінній $cs$ .

int cs = 1;

Читаємо вхідні дані доти, поки значення $N$ більше нуля.

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

Для кожного значення $N$ обчислюємо результат за формулою і виводимо його разом з номером тесту.

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

Java реалізація

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

Java