MENGHITUNG PERSEGI
Tahukah kamu bahwa grid berukuran 3x4 sebagai berikut memiliki 20 persegi (segi empat sama sisi)?

Diberikan N and M, tentukan banyaknya persegi yang terdapat pada grid berukuran NxM.
Batasan :
1 N,M
100.000
Format Input :
N M
Format Output :
Sebuah bilangan yang menyatakan banyaknya persegi yang terdapat pada grid berukuran NxM.
Sample input dan output :
| 3 4 | 20 |
| 4 3 | 20 |
| 1 10 | 10 |
| 5 5 | 55 |
Banyaknya persegi 1x1 pada grid n x m adalah n*m.
Banyaknya persegi 2x2 pada grid n x m adalah (n-1)*(m-1)
Banyaknya persegi 3x3 pada grid n x m adalah (n-2)*(m-2)
Begitu seterusnya hingga (n-k)*(m-k) bernilai 0.
Cara 1 – O(N) :
Cukup gunakan looping. Karena nilai n dan m bisa sangat besar, maka tipe data yang harus digunakan untuk menampung jumlah persegi haruslah integer 64 bit (int64 pada pascal atau long long pada C++).
var
n, m : longint;
jumlah : int64;
begin
readln(n, m);
while (n > 0) or (m > 0) do
begin
jumlah := jumlah + n*m;
dec(n); dec(m);
end;
writeln(jumlah);
end.
Cara 2 – O(1) :
Misalkan n <= m. Perhatikan bahwa untuk cara yang di atas sebenarnya sama saja dengan menghitung 1*(m-n+1) + 2*(m-n+2) + .... + k*(m-n+k) sehingga kita bisa menurunkan rumus seperti ini.
var
n, m, temp : int64;
jumlah : int64;
begin
readln(n, m);
if (n > m) then
begin
temp := n;
n := m;
m := temp;
end;
jumlah := (n*(n+1)*(3*m - n + 1)) div 6;
writeln(jumlah);
end.
kalo n=100000, m=100000, gk cukup lho int64.
kan 100000^2 + 99999^2 + ... + 1^2 >10^19
harus pake bignum deh
hitung m*n -> ubah ke string
hitung (m-1)*(n-1) -> ubah ke string
dst...
trus pake penjumlahan bignum dapet deh jawabannya
Masuk untuk menulis jawaban
while(x!=0 and y!=0)
{
has+=x*y;
x--; y--;
}
cout<<has<<endl;
}
#include <stdio.h>
using namespace std;
int persegi(int n, int m)
{
return (m * (m + 1) * ((3* N) - M +1 )) / 6;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d",persegi(n,m));
return 0;
}
Pakai rumus ,cari - cari di Internet.
var
n,m,t,a:integer;
begin
a:=0;
repeat
t:=n*m;
a:=a+t;
n:=n-1;
m:=m-1;
until (n<1) or (m<1);
writeln(a);
readln;
end.
//Dengan c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin >> n >> m;
if(n < m)
{
int k = 0;
for(int i=1;i<=n;i++)
{
k += ((n-i)+1)*((m-i)+1);
}
cout << k << "\n";
}
else if(m < n)
{
int k = 0;
for(int i=1;i<=m;i++)
{
k += ((n-i)+1)*((m-i)+1);
}
cout << k << "\n";
}
else if(m == n)
{
int k = 0;
for(int i=1;i<=m;i++)
{
k += ((n-i)+1)*((m-i)+1);
}
cout << k << "\n";
}
return 0;
}
mas faris misal gini mas gimana
begin
readln(m,n);
jumlah:=0;
for i:= 1 to m do begin
jumlah:=jumlah+m*n;
dec(m); dec (n);
end;
writeln(jumlah);
end.