My first Magazine pemrograman-kompetitif-dasar | Page 16

1 Perkenalan Pemrograman Kompetitif
√
merupakan bilangan kuadrat, artinya N
dapat dibagi habis oleh N. Khusus pembagi akar ini
√
tidak memiliki pasangan, karena √ N N = N. Perhatikan contoh berikut:
Jika N = 16, maka:
• Karena 1 membagi habis 16, maka
• Karena 2 membagi habis 16, maka
• 4 membagi habis 16, tetapi karena
16
1 = 16 juga membagi habis 16
16
2 = 8 juga membagi habis 16
16
4 juga 4, maka pembagi ini tidak
memiliki pasangan.
Maka kita bisa simpulkan bahwa lampu menyala jika dan hanya jika N merupakan bilangan
kuadrat. Untuk √ menentukan apakah N merupakan bilangan kuadrat, kita dapat menghitung
pembulatan dari N, sebut saja s. Kemudian menghitung s × s lagi. Jika kita mendapatkan kembali
N, maka N adalah bilangan kuadrat.
Sebagai contoh:
√
• N = 8, maka 8 ≈ 2.828427, dibulatkan menjadi 3. Hasil dari 3 × 3 bukan 8, maka 8 bukan
bilangan kuadrat.
√
• N = 9, maka 9 = 3, dibulatkan menjadi 3. Hasil dari 3 × 3 adalah 9, maka 9 adalah bilangan
kuadrat.
√
• N = 10, maka 10 ≈ 3.162277, dibulatkan menjadi 3. Hasil dari 3 × 3 bukan 10, maka 10
bukan bilangan kuadrat.
Implementasinya sangat sederhana:
# include < iostream >
# include < cmath >
using namespace std ;
int main () {
long long N ;
cin >> N ;
long long s = round ( sqrt ( N ));
if ( s * s != N ) {
cout << " lampu ␣ mati " << endl ;
} else {
cout << " lampu ␣ menyala " << endl ;
}
}
Program ini tidak memiliki perulangan sama sekali, dan hanya memanggil fungsi bawaan C++
untuk mengakarkan bilangan. Program di atas dapat menyelesaikan permasalahan hingga kasus
terbesar N = 10 18 hanya dalam hitungan milisekon saja!
Melalui penyelesaian soal ini, kita mempelajari bahwa solusi yang naif belum tentu cukup
untuk menyelesaikan soal. Bahkan, solusi yang lebih rumit belum tentu mendapatkan penilaian
sempurna. Dibutuhkan analisis yang mendalam hingga didapatkan strategi penyelesaian yang
efisien.
6