My first Magazine pemrograman-kompetitif-dasar | Page 13

1.3 Contoh Soal Pemrograman Kompetitif
Pada contoh kedua, tombol yang mempengaruhi keadaan lampu adalah tombol 1, tombol
2, dan tombol 4. Penekanan tombol 1 mengakibatkan lampu menjadi menyala, penekanan
tombol 2 mengembalikannya ke keadaan mati, dan penekanan tombol 4 menjadikan lampu
kembali menyala.
Batasan
• 1 ≤ N ≤ 10 18
Seperti yang tertera pada contoh soal Lampu dan Tombol, soal pemrograman kompetitif
memiliki batasan-batasan yang jelas. Pada soal tersebut, tertera bahwa batasan waktu adalah 1
detik. Artinya, program Anda harus memiliki running time tidak melebihi 1 detik. Batasan memori
64 MB menyatakan bahwa program Anda juga tidak boleh memakan memori lebih dari batasan
tersebut. Terakhir, terdapat batasan masukan, yakni berupa 1 ≤ N ≤ 10 18 . Artinya program Anda
diharuskan dapat menyelesaikan soal tersebut untuk nilai N yang diberikan. Batasan ini juga
menjamin bahwa program Anda tidak akan diuji dengan nilai-nilai di luar batasan.
1.3.1
Solusi Sederhana
Strategi yang paling sederhana adalah dengan menyimulasikan skenario pada deskripsi soal:
•
•
•
•
Mulai dari tombol ke-1, dipastikan keadaan lampu akan berubah (N habis dibagi 1).
Lanjut ke tombol ke-2, periksa apakah 2 habis membagi N. Bila ya, ubah keadaan lampu.
Lanjut ke tombol ke-3, periksa apakah 3 habis membagi N. Bila ya, ubah keadaan lampu.
... dan seterusnya hingga tombol ke-N.
Setelah selesai disimulasikan, periksa keadaan lampu ruangan ke-N dan cetak jawabannya.
Berikut adalah implementasi solusi sederhana ini dalam C++:
# include < iostream >
using namespace std ;
int main () {
long long N ;
cin >> N ;
int divisorCount = 0;
for ( long long i = 1; i <= N ; i ++) {
if ( N % i == 0) {
divisorCount ++;
}
}
if ( divisorCount % 2 == 0) {
cout << " lampu ␣ mati " << endl ;
} else {
cout << " lampu ␣ menyala " << endl ;
}
}
3