Количество
диагоналей у выпуклого n - угольника не менее N. Чему равно минимально
возможное значение n?
Вход. Каждая входная стока содержит положительное целое число N
(N £ 1015) – количество проведенных диагоналей.
Значение N = 0 является концом входных данных и не обрабатывается.
Выход. Для каждого
теста выведите его номер и минимально возможное число n сторон
многоугольника.
Пример
входа |
Пример
выхода |
10 100 1000 0 |
Case 1: 7 Case 2: 16 Case 3: 47 |
математика
Каждая точка
многоугольника соединена отрезками с n – 1 остальными
точками. Эти отрезки образуют 2 стороны и n – 3 диагонали. Поскольку точек в многоугольнике n,
а из каждой точки исходит n – 3
диагонали, то количество диагоналей
выпуклого n – угольника равно n * (n – 3) / 2 (каждая
диагональ подсчитывается дважды).
Если n *
(n – 3) / 2 = N, то значение n находим из квадратного уравнения
n2 – 3 * n –
2 * N = 0
Положительный
корень уравнения равен
Остается
округлить сверху вычисленное значение. Поскольку N £ 1015, то вычисления следует проводить, используя
тип данных long long.
Пример
Рассмотрим
второй тест. Для N = 100 получим
n = = 16
Читаем входные
данные пока N > 0, вычисляем по формуле результат и выводим его с номером
теста.
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 реализация
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++;
}
}
}