BNPCHS 2009

A - Bujur Sangkar Ajaib

Author: Ryan Leonel Somali

Soal ini adalah soal termudah di babak penyisihan. Yang perlu kita lakukan hanya menjumlahkan 1 sampai n² kemudian bagi hasilnya dengan n. Untuk n <= 100, solusi O(n²) dengan menjumlahkan semua bilangan dari 1 hingga n² sudah cukup untuk mendapatkan accepted. Namun jika anda mau, solusi soal ini bisa dioptimasi menjadi O(1) dengan rumus:

ans = (1 + 2 + 3 + ... + n²) / n
ans = (n² * (n² + 1) / 2) / n
ans = n * (n² + 1) / 2

Total 43 peserta berhasil menyelesaikan soal ini.

Solusi C/C++
oleh Ryan Leonel Somali

#include <stdio.h>
int main()
{
  int n, T;
  scanf( "%d", &T );
  while ( T-- )
  {
    scanf( "%d", &n );
    printf( "%d\n", (n * n + 1) * n / 2 );
  }
}

Solusi PASCAL
oleh Eko Wibowo

var i, n, T, x : longint;
begin
  read(T);
  for i := 1 to t do
  begin
    read(n);
    x := ((n * n + 1) * n) div 2;
    writeln(x);
  end;
end.