Hak Cipta Dilindungi Undang-undang
SOAL UJIAN OLIMPIADE SAINS NASIONAL 2013 CALON PESERTA INTERNATIONAL OLYMPIAD IN INFORMATICS (IOI) 2014 SESI LATIHAN
INFORMATIKA Waktu : 5 jam
KEMENTERIAN PENDIDIKAN DAN KEBUDAYAAN DIREKTORAT JENDERAL PENDIDIKAN MENENGAH DIREKTORAT PEMBINAAN SEKOLAH MENENGAH ATAS TAHUN 2013
Menimbang & Mengurutkan Batas Waktu: 1 detik Batas Memori: 32 MB
Deskripsi Pak Dengklek memiliki N ekor bebek yang dikumpulkan di sebuah kandang yang besar. Bebek-bebek tersebut dinomori 1 sampai dengan N. Uniknya, berat dari bebek-bebek tersebut berbeda-beda; yakni, tidak ada dua bebek dengan berat yang sama persis. Namun, sampai saat ini Pak Dengklek tidak tahu berat masing-masing bebeknya. Ia ingin memisahkan bebek-bebek tersebut ke dalam N buah kandang baru yang dijejerkan dari kiri ke kanan. Satu kandang berisi satu bebek. Ia juga ingin agar bebek di kandang paling kiri adalah bebek teringan, bebek di kandang kedua terkiri adalah bebek teringan kedua, dan seterusnya sampai bebek di kandang paling kanan adalah bebek terberat. Tentunya, untuk melakukan hal tersebut, Pak Dengklek harus menimbang bebek-bebeknya. Namun, ia hanya memiliki sebuah timbangan dua lengan. Untuk menggunakan timbangan tersebut, Pak Dengklek harus meletakkan seekor bebek pada masing-masing lengan. Kemudian, timbangan tersebut akan memberi tahu bebek pada lengan mana yang lebih ringan. Karena timbangan tersebut sudah agak usang, Pak Dengklek hanya bisa melakukan penimbangan paling banyak K kali. Bantulah Pak Dengklek menimbang bebek-bebeknya sedemikian sehingga ia dapat menempatkan bebek-bebeknya pada kandang baru yang sesuai.
Format Interaksi Soal ini adalah soal interaktif. Pada awalnya, program Anda harus membaca string "Subsoal X" dengan X menyatakan nomor subsoal dari kasus uji yang sedang diujikan. Berikutnya program Anda dapat membaca dua buah bilangan bulat N dan K. Kemudian, sebanyak maksimum K kali, Anda dapat mengeluarkan perintah dalam sebuah baris dengan format: timbang B1 B2 yang artinya Anda menaruh bebek nomor B1 pada lengan kiri neraca dan bebek nomor B2 pada lengan kanan neraca. Untuk melakukan perintah ini, harus berlaku 1 ≤ B1, B2 ≤ N dan B1 ≠ B2. Setelah itu, program Anda dapat membaca sebuah bilangan -1 atau 1. Bilangan -1 menandakan bahwa bebek B1 lebih ringan daripada bebek B2, sedangkan 1 menandakan sebaliknya. Anda juga dapat mengeluarkan perintah dalam sebuah baris dengan format: jawab B1 B2 ... BN yang artinya Anda sudah mengetahui semua urutan relatif bebek-bebek dan Anda memutuskan bahwa bebek nomor Bi adalah bebek teringan ke-i. Setelah itu, interaksi akan otomatis dihentikan. Jika urutan yang Anda tebak memang sesuai dengan urutan bebek yang sebenarnya, Anda akan dinyatakan benar untuk kasus uji tersebut. Namun jika tebakan Anda 1
tidak sesuai, Anda dinyatakan salah dan tidak akan mendapat nilai untuk subsoal tersebut.
Contoh Interaksi Keluaran Program Peserta
Umpan Balik Grader Subsoal 0 3 3
timbang 1 2 1 timbang 2 3 -1 timbang 3 1 1 jawab 2 1 3 (interaksi selesai)
Penjelasan Contoh Interaksi Pak Dengklek memiliki 3 ekor bebek. Bebek nomor 2 adalah bebek teringan, bebek nomor 1 adalah bebek teringan kedua, dan bebek nomor 3 adalah bebek terberat.
Pembagian Subsoal Subsoal 1 (15 poin) N = 5. K = 15. Subsoal 2 (20 poin) N = 7. K = 28. Subsoal 3 (25 poin) N = 12. K = 56. Khusus untuk subsoal 1 sampai dengan subsoal 3: Hanya terdapat sebuah kasus uji (satu subsoal dinyatakan oleh satu kasus uji), yang dapat dimainkan di sini. Dalam permainan tersebut, banyaknya pertanyaan yang dapat diajukan tidak dibatasi. Jika Anda sudah memenangkan permainan untuk subsoal tertentu, Anda dapat 2
memilih pilihan pada permainan untuk mengeluarkan source code yang dapat langsung Anda kirimkan ke grader dan menjawab dengan benar pada subsoal yang telah Anda menangkan. Subsoal 4 (40 poin) 1 ≤ N ≤ 100. K = 1.000.
Catatan Yang perlu diperhatikan adalah bahwa untuk tipe soal interaktif seperti ini, Anda harus selalu memberikan perintah "fflush(stdout);" (bagi pengguna C/C++) atau "flush(output);" (bagi pengguna PASCAL) setiap kali Anda mencetak keluaran (dengan kata lain, setiap kali ada perintah mencetak keluaran misalnya write, writeln, printf, cout, atau puts, tepat di bawahnya harus ada perintah fflush/flush). Sebagai contoh, berikut adalah contoh source code dalam bahasa Pascal yang akan selalu menjawab konfigurasi "1 2 3" tanpa mempedulikan nilai N dan K yang diberikan. var subsoal: string; N, K: longint;
begin readln(subsoal); readln(N, K);
writeln('jawab 1 2 3'); flush(output); end.
Dan berikut adalah contoh source code dalam bahasa C++. #include
#include
char subsoal[100]; int nomor; int N, K;
int main() {
3
scanf("%s %d", subsoal, &nomor); scanf("%d %d", &N, &K);
printf("jawab 1 2 3\n"); fflush(stdout);
return 0; }
Peringatan Apabila program Anda melakukan salah satu dari hal-hal di bawah ini: mengeluarkan perintah tidak sesuai syarat sehingga tidak dikenali oleh grader, atau menimbang dengan nomor bebek yang sama di kedua sisi lengan neraca (misal 'timbang 2 2'), atau menimbang lebih dari K kali, maka program Anda akan dihentikan secara otomatis dan Anda tidak memperoleh nilai pada kasus uji yang bersangkutan.
4
Fractran Batas Waktu: 1 detik Batas Memori: 32 MB
Deskripsi Sebuah model komputasi alternatif bernama Fractran menggunakan representasi bilangan pecahan untuk menyatakan proses komputasi. Dalam model ini, sebuah program adalah sebuah barisan berhingga dari bilangan-bilangan pecahan, sedangkan masukan dan keluaran adalah sebuah bilangan bulat positif. Proses komputasi berjalan sebagai berikut: 1. Pilih bilangan pertama pada program yang jika dikalikan dengan masukan akan menghasilkan bilangan bulat. Kemudian, ganti masukan dengan bilangan hasil perkalian tersebut. 2. Ulangi langkah pertama sampai tidak ada bilangan pada program yang jika dikalikan dengan masukan akan menghasilkan bilangan bulat. 3. Bilangan hasil perkalian terakhir adalah keluaran dari proses komputasi ini. Sebagai contoh, misalkan kita mempunyai program = (4⁄3, 2⁄5, 1⁄7) dan masukan = 45. Proses komputasi berjalan sebagai berikut: 3 (yakni, penyebut dari 4⁄3) membagi 45, maka masukan diganti dengan 45 × 4⁄3 = 60. Karena 60 juga habis dibagi 3, maka masukan diganti dengan 60 × 4⁄3 = 80. Karena 80 tidak habis dibagi 3, maka kita cek pecahan kedua: 2⁄5. Ternyata 5 membagi 80, sehingga masukan diganti dengan 80 × 2⁄5 = 32. Tidak ada pecahan lagi yang bisa dipakai, sehingga komputasi berhenti dengan nilai keluaran = 32. Anda diberikan sebuah bilangan bulat N. Buatlah sebuah program dalam model komputasi Fractran yang akan mengubah masukan N menjadi keluaran M, dengan M merupakan hasil perkalian dari semua faktor prima N.
Format Masukan Baris pertama pada berkas masukan berisi string "Subsoal X" (tanpa tanda kutip) dengan X menyatakan nomor subsoal. Baris kedua berisi sebuah bilangan bulat N.
Format Keluaran Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyaknya pecahan yang menyusun program. T baris berikutnya masing-masing berisi sebuah pecahan yang menyusun program, terurut dari awal hingga akhir. Pecahan ditulis sebagai pembilang dan penyebut (masing-masing berupa bilangan bulat) yang dipisahkan oleh garis miring ('/'). Program yang Anda keluarkan harus memenuhi semua syarat berikut: 1 ≤ T ≤ 1.000 Selama proses komputasi, bilangan hasil perkalian masukan dan bilangan pecahan yang memenuhi syarat tidak pernah melebihi 263 – 1. Proses komputasi harus berhenti pada suatu saat. 5
Contoh Masukan Subsoal 0 200
Contoh Keluaran 3 1/4 3/25 5/3
Penjelasan Contoh Kasus Uji Pada contoh masukan di atas, N = 200. Faktor-faktor prima dari 200 adalah 2 dan 5, sehingga M = 2 × 5 = 10. Proses komputasi dengan masukan N = 200 dan keluaran M = 10 berjalan sebagai berikut: 200 × 1⁄4 = 50 50 × 3⁄25 = 6 6 × 5⁄3 = 10
Pembagian Subsoal Subsoal 1 (9 poin) Hanya terdapat sebuah kasus uji, yang dapat diunduh di sini. Subsoal 2 (9 poin) Hanya terdapat sebuah kasus uji, yang dapat diunduh di sini. Subsoal 3 (24 poin) 2 ≤ N ≤ 50. Subsoal 4 (28 poin) 2 ≤ N ≤ 500. Subsoal 5 (30 poin) 2 ≤ N ≤ 109.
6
Tukar-Tukar Batas Waktu: 2 detik Batas Memori: 256 MB
Deskripsi Pak Dengklek memiliki sebuah tabel berukuran M × N, di mana M menyatakan banyaknya baris dan N menyatakan banyaknya kolom. Baris dinomori dari 1, 2, hingga M, secara berurutan dari atas ke bawah. Sedangkan kolom dinomori dari 1, 2, hingga N secara berurutan dari kiri ke kanan. Masing-masing sel dari tabel itu berisi sebuah bilangan bulat dalam rentang 0 hingga 1.000. Sebanyak maksimum K kali, Anda dapat menukar isi dari dua sel yang bersisian. Dua buah sel dikatakan bersisian apabila salah satu sel berada di atas, bawah, kiri, atau kanan sel lain dan kedua sel berdempetan. Bantulah Pak Dengklek melakukan maksimum K pertukaran tersebut agar total dari semua selisih pasangan sel yang bersisian seminimum mungkin.
Format Masukan Baris pertama masukan berisi string "Subsoal X" di mana X menyatakan nomor subsoal. Baris kedua berisi tiga buah bilangan bulat M, N, dan K yang terpisah oleh spasi. Sebanyak M baris berikutnya, masing-masing berisi tepat N bilangan bulat terpisah spasi, masingmasing berada di antara 0 hingga 1.000 (inklusif, termasuk 0 dan 1.000).
Format Keluaran Baris pertama keluaran berisi sebuah bilangan bulat Y yang menyatakan banyaknya pertukaran. Sebanyak Y baris berikutnya masing-masing berisi empat buah bilangan bulat terpisah spasi: r1, c1, r2, c2, yang menyatakan penukaran isi dari sel pada baris r1 dan kolom c1 dengan sel pada baris r2 dan kolom c2. Keluaran dapat memperoleh nilai lebih dari nol hanya apabila 0 ≤ Y ≤ K, dan masing-masing dari r1, c1, r2, c2 pada masing-masing baris mewakili dua sel yang benar-benar berada pada tabel dan bersisian.
Penilaian Program Anda akan diuji dengan 18 buah kasus uji resmi. Masing-masing kasus uji dibangkitkan secara acak menurut sebuah bilangan umpan (seed) tertentu. Secara sederhana, sebuah umpan akan menghasilkan sebuah kasus uji tersendiri. Anda dapat mengunduh program untuk menguji solusi Anda secara offline di sini. Penguji ini menggunakan pustaka pembangkit bilangan acak semu yang menjadi default di bahasa C++. Untuk menggunakan penguji ini, pertama-tama letakkan berkas program di satu direktori yang sama dengan berkas kode sumber solusi Anda. Lalu buka Command Prompt (untuk Windows) atau Terminal (untuk Linux) dan tuju direktori tersebut (dengan menggunakan perintah cd). Kemudian, jalankan perintah: ./penguji <program>
(Anda mungkin harus menghapus "./" pada Windows.)
7
Di sini, adalah bilangan bulat non-negatif sebagai umpan pembangkit bilangan acak semu, dan <program> adalah perintah untuk menjalankan program solusi Anda (seperti "./solusi" pada Linux atau "solusi.exe" pada Windows). Contohnya pada Linux: ./penguji 123 ./solusi
Dan pada Windows: penguji.exe 123 solusi.exe
Setelah itu, Anda dapat melihat nilai Anda untuk kasus uji tersebut pada layar. Nilai Anda adalah 10.000.000 dikurangi total dari jumlah semua selisih sel-sel bersisian dari semua kasus uji.
Contoh Masukan Subsoal 0 3 3 100 1 2 3 4 5 6 7 8 9
Contoh Keluaran 1 2 2 3 2
Penjelasan Contoh Kasus Uji Nilai untuk kasus uji di atas adalah 9.999.965. Apabila tidak terjadi pertukaran, nilai yang diperoleh untuk matriks pada contoh masukan adalah: 10.000.000-(|1-2|+|2-3|+|1-4|+|2-5|+|3-6|+|4-5|+|5-6|+|4-7|+|5-8|+|6-9|+|7-8|+|8-9|)
yang sama dengan 9.999.976. Penulisan |x| menyatakan harga mutlak dari x. Harga mutlak dari x didefinisikan sebagai x apabila x adalah bilangan positif, atau -x apabila x bukan bilangan positif. Sedangkan, hasil pertukaran sel pada baris 2 kolom 2 dengan sel pada baris 3 kolom 2 akan menghasilkan matriks: 1 2 3 4 8 6 7 5 9
Nilai yang diperoleh adalah: 10.000.000-(|1-2|+|2-3|+|1-4|+|2-8|+|3-6|+|4-8|+|8-6|+|4-7|+|8-5|+|6-9|+|7-5|+|5-9|)
yang sama dengan 9.999.965.
8
Pembagian Subsoal Untuk semua subsoal, berlaku batasan: 1 ≤ M ≤ 100. 1 ≤ N ≤ 100. 1 ≤ K ≤ 10.000. Subsoal 1 Hanya terdapat satu kasus uji, yang dapat diunduh di sini. Perhitungan poin yang Anda dapat di subsoal ini adalah dengan menggunakan formula berikut.
Subsoal 2 Perhitungan poin yang Anda dapat di subsoal adalah dengan menggunakan formula berikut.
9
