Olimpiade Sains Provinsi (OSP) 2015 - Komputer, Nomor 50
Pak Dengklek memiliki sebuah array berisi N bilangan bulat non-negatif. Pak Dengklek pun menantang Anda untuk memilih angka-angka dari arraynya yang jika dijumlahkan habis dibagi N. Tentu saja angka di suatu index tidak boleh dipilih lebih dari sekali. Apabila hal ini mungkin, beritahu Pak Dengklek berapa banyak angka yang Anda ambil dan apa saja angka-angkanya. Apabila hal ini tidak mungkin, katakan "Tidak mungkin".
Format Input :
- Baris pertama berisi sebuah bilangan bulat N (2 <= N <= 100000)
- Baris kedua berisi N bilangan bulat non-negatif yang menyatakan isi array Pak Dengklek
Format Output :
- Apabila mungkin, pada baris pertama keluarkan sebuah angka yang menyatakan banyaknya angka yang Anda ambil dari array Pak Dengklek, dan pada baris kedua keluarkan angka-angka yang Anda ambil dipisahkan oleh sebuah spasi.
- Apabila tidak mungkin, pada baris pertama keluarkan sebuah string "Tidak mungkin" tanpa tanda petik.
| Contoh Masukan | Contoh Keluaran |
|
3 |
2 4 2 |
| 3 4 4 4 |
3 4 4 4 |
1 jawaban
Muhammad Ayaz Dzulfikar11 tahun lalu
Aku noob
7
Sebenarnya jawaban "Tidak Mungkin" itu tidak mungkin ada. Selain itu, untuk tiap masukan, pasti ada suatu solusi, di mana angka yang dipakai merupakan angka-angka yang berurutan.
Pertama, perhatikan properti berdasarkan modulo. Jika mengambil array dari indeks ke (j + 1),(j + 2), ... , (k), pasti berlaku : sum(0,j) mod n == sum(0,k) mod n, di mana sum(a,b) artinya array[a] + array[a + 1] + ... + array[b]. Oh iya, untuk mempermudah sebut prefix sum. sum dimulai dari 0 juga akan mempermudah penjelasan selanjutnya.
Kemudian, perhatikan bahwa kita memiliki n + 1 prefix sum berbeda, yakni prefix kosong atau sum(0,0), prefix 1 atau sum(0,1) dst sampai prefix n atau sum(0,n).
Terakhir, modulo n akan memiliki n buah kemungkinan hasil, yakni 0,1,2,...,n - 1. Sedangkan kita memiliki n + 1 prefix sum. Berdasarkan Pigeon Hole Principle, pasti terdapat setidaknya 1 nilai modulo yang muncul pada 2 prefix berbeda. Dengan kata lain, pasti ada solusi di mana angka yang dipakai merupakan angka-angka yang muncul berurutan.
Potongan source code (aku gak ngerti pseudocode enaknya nulis gimana)
int n;
int arr[100001];
int index[100001];
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++){
scanf("%d",&arr[i]);
index[i] = -1; // inisialisasi biar gak 2 kali bikin for
}
index[0] = 0;
int sum = 0;
for(int i = 1 ; i <= n ; i++){
sum = (sum + arr[i]) % n;
if(index[sum] == -1) // belum ada
index[sum] = i;
else{ // udah ada
printf("%d\n",i - index[sum]);
printf("%d",arr[index[sum] + 1]);
for(int j = index[sum] + 2 ; j <= i ; j++)
printf(" %d",arr[j]);
printf("\n");
break;
}
}
Muhammad Ayaz Dzulfikar11 tahun lalu
Aku noob
biar gak ribet anggap aja index[sum] = k ya
kan prefix-k modnya sama dengan prefix-i, jadinya berdasarkan penjelasanku sebelumnya, yang diambil dari k + 1,k + 2,...,i - 1,i. Panjangnya kan artinya i - k
Selanjutnya tinggal masalah outputnya aja. Karena udah ketemu solusi, gak usah dilanjutin, langsung break aja.
Saiz Kurniawan11 tahun lalu
Aku adalah Jelly, Kita adalah Jelly
Halo kak, kenapa tidak pake knapsak aja kak ? Pigeon Hole Principle itu apa kak ?
Muhammad Ayaz Dzulfikar11 tahun lalu
Aku noob
knapsack butuh memori sama waktu O(N^2), walaupun gak dijelaskan secara eksplisit, menurutku pembuat soal ini pengen solusi yang gak MLE maupun TLE di CP. Solusi di atas O(N) doang
PHP menurutku lebih baik kamu googling aja
Saiz Kurniawan11 tahun lalu
Aku adalah Jelly, Kita adalah Jelly
Oh gitu ya kak. PHP itu bahasa ya kak.
Kode yang kakak tulis itu pake bahasa PHP juga ya ? Kalo buat OSP harus bisa bahasa apa aja kak ? :v /
xxxxx xxxxx10 tahun lalu
Kak bagian
for(int j = index[sum] + 2 ; j <= i ; j++)
printf(" %d",arr[j]);
knp harus j=index[sum]+2 bukan index[sum]+1?
Windra Swastika10 tahun lalu
Pseudo-code-nya apa nggak kurang?
Gimana kalo misal pada array[1] sudah merupakan bilangan % n == 0?
Di pseudo-code di atas, array dimulai dari 1, sehingga jika
sum = (sum + arr[i]) % n
dan sum = 0, maka index[0] tidak tersedia.
Masuk untuk menulis jawaban
permisi kak, mau nanya, yang bagian else yang sudah ada itu bisa tolong dijelasin gak kak maksudnya gimana? Aku gak mudeng euy._. hehe makasih banyak sebelumnya kak :)