Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 42
OLEH-OLEH BATU GIOK
Pak Blangkon baru saja kembali ke Negeri TOKI. Karena kangen dengan Pak Dengklek, diapun berencana memberikan oleh-oleh berupa N buah batu giok. Setiap giok ke-i memiliki berat Bi. Pak Blangkon tahu bahwa Pak Dengklek hanya mau menerima sekumpulan batu giok jika memiliki berat yang berbeda-beda dan faktor perseketuan terbesar berat dari sekumpulan batu giok tersebut bernilai sama dengan 1.
Diberikan sekumpulan N batu giok dengan berat masing-masing Bi (1 <= i <= N). Anda diminta untuk membuat sebuah program yang menentukan apakah sekumpulan batu giok layak sebagai hadiah sesuai dengan keinginan Pak Dengklek.
Format Masukan:
Masukan terdiri dari 2 baris. Baris pertama berisi bilangan bulat N. Baris kedua berisi N buah bilangan Bi yang menyatakan berat giok ke-i yang dipisahkan dengan spasi.
Format Keluaran:
Tuliskan LAYAK jika berat sekumpulan N batu giok tersebut sesuai dengan keinginan Pak Dengklek. Sebaliknya tuliskan TIDAK LAYAK.
Batasan:
- 2 <= N <= 10.000
- 2 <= Bi <= 100.000
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|
2 10 15 |
TIDAK LAYAK |
|
3 50 625 75 |
TIDAK LAYAK |
|
3 7 9 11 |
LAYAK |
|
5 2 3 7 11 17 |
LAYAK |
3 jawaban
Hocky Yudhiono7 tahun lalu
Cupu :(
1
Diketahui sifat FPB berikut gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).
Untuk mencari fpb dua buah bilangan, dapat digunakan algoritma Euclid.
include <iostream>
using namespace std;
int N,B,FPBnow;
bool Sudah[100005];
int fpb(int x, int y){
if(x%y == 0) return y; //Fungsi yang mengembalikan FPB(a,b)
return fpb(y,x%y);
}
int main(){
cin >> N; //Input jumlah batu
for(int i = 1;i <= N;i++){ //Untuk setiap batu
cin >> B; //Input berat batu
if(Sudah[B]){ //Jika batu yang berat B sudah pernah ada
cout << "TIDAK LAYAK" << endl; //Maka tidak layak
return 0; //Program berhenti
}
Sudah[B] = 1; //Tandai berat B sudah pernah ada
if(i == 1) FPBnow = B; //Jika ini batu pertama, maka FPBnya berat batu itu sendiri
else FPBnow = fpb(B,FPBnow); //Selain itu, maka kita cari FPB antara batu saat ini dengan batu yang lain
}
if(FPBnow == 1) cout << "LAYAK" << endl; //Jika FPB nya 1, maka batunya layak
else cout << "TIDAK LAYAK" << endl; //Jika tidak, maka tidak layak
}
m irfan firmansyah7 tahun lalu
1
boleh pake __gcd() gak sih???
Masuk untuk menulis jawaban