Diaqonal (Həll təhlili)

Hər bir konveks çoxbucaqlının zirvələri qalan n - 1 zirvə ilə seqmentlərlə birləşdirilir. Bunlardan ikisi tərəf, qalan n - 3 isə diagonallardır. Çünki ümumi $n$ zirvə var və hər birindən n - 3 diagonal çıxır, bu zaman konveks $n$-bucaqlıda ümumi diagonal sayı n \cdot (n - 3) / 2 olur (çünki hər bir diagonal iki dəfə sayılır).

Əgər n * (n - 3) / 2 = N, o zaman $n$ dəyəri kvadrat tənlikdən tapıla bilər:

Bu tənliyin müsbət kökü

Bu dəyəri yaxın tam ədəddə yuvarlaqlaşdırmaq qalır. N \le 10^{15} olduğu üçün, bütün hesablamalar long long məlumat tipi ilə aparılmalıdır.

Misal

İkinci testi nəzərdən keçirək. N = 100 üçün alırıq

Alqoritmin həyata keçirilməsi

Cari testin nömrəsini $cs$ dəyişənində saxlayacağıq.

int cs = 1;

Giriş məlumatlarını oxuyuruq, $N$ dəyəri sıfırdan böyük olduğu müddətdə.

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

Hər bir $N$ dəyəri üçün nəticəni formuldan hesablayıb, testin nömrəsi ilə birlikdə çıxarırıq.

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

Java realizasiyası

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