PARROTS. Burung Kakatua. International Olympiad in Informatics July 2011, Pattaya City, Thailand Competition Tasks Day 2 Indonesia 1

International Olympiad in Informatics 2011 22–29 July 2011, Pattaya City, Thailand Competition Tasks – Day 2

PARROTS Indonesia 1.3

Burung Kakatua Yanee adalah seseorang yang tertarik pada burung. Sejak membaca tentang IP over Avian carriers (IPoAC), ia telah meluangkan banyak waktunya untuk melatih sekumpulan burung kakatua yang cerdas untuk membawa pesan jarak jauh. Impian Yanee adalah untuk memanfaatkan burung-burungnya untuk mengirim pesan M ke tempat yang sangat sangat jauh. Pesan M adalah sederetan N (tidak harus unik) bilangan bulat, setiap bilangan bulat bernilai antara 0 dan 255, inklusif. Yanee merawat K burung kakatua yang terlatih secara khusus. Semua burung kakatua terlihat sama. Yanee tidak dapat membedakan satu burung dengan burung lainnya. Setiap burung kakatua dapat mengingat satu bilangan bulat antara 0 dan R, inklusif. Pada tahap awal, ia mencoba sebuah skema sederhana: untuk mengirim pesan, Yanee melepas burung kakatua dari sarangnya satu per satu. Sebelum burung kakatua meluncur ke udara, ia mengajarkannya suatu angka dari deretan pesan secara terurut. Sayangnya, cara ini tidak berjalan dengan baik. Ternyata, semua burung kakatua sampai ke tujuan, namun urutan sampainya burung mungkin berbeda dengan urutan keberangkatannya. Dengan skema ini, Yanee dapat memperoleh kembali semua angka yang dikirimkannya, tetapi tidak bisa mendapatkannya sesuai urutan yang benar. Untuk merealisasikan mimpinya, Yanee membutuhkan cara yang lebih baik, dan untuk itu ia membutuhkan bantuan Anda. Diberikan sebuah pesan M, ia berencana melepaskan burungnya satu per satu seperti sebelumnya. Yanee membutuhkan Anda untuk menulis sebuah program yang mampu melakukan dua operasi sebagai berikut:  Pertama, program Anda harus dapat membaca pesan M dan mengubahnya menjadi deretan sebanyak-banyaknya K bilangan bulat antara 0 dan R yang akan ia ajarkan kepada burungnya.  Kedua, program Anda harus dapat membaca deretan bilangan bulat antara 0 dan R yang diterima sesuai dengan urutan sampainya burung, dan mengubahnya kembali ke pesan M. Anda dapat mengasumsikan bahwa semua burung kakatua pasti sampai ke tempat tujuan, dan masing-masing dapat mengingat angka yang disampaikan padanya. Yanee mengingatkan Anda sekali lagi bahwa burung dapat sampai dengan urutan sembarang. Perhatikan bahwa Yanee hanya mempunyai K burung kakatua, maka deret bilangan bulat antara 0 dan R yang Anda hasilkan harus berisi paling banyak K bilangan bulat.

Halaman 1 dari 6



Tugas Anda Tuliskan dua prosedur terpisah. Salah satunya akan digunakan oleh pengirim (encoder) dan yang lainnya akan digunakan oleh penerima (decoder).

Keseluruhan proses dapat diilustrasikan pada gambar berikut. Kedua prosedur yang Anda tulis adalah:  Prosedur encode(N,M) yang mempunyai parameter sebagai berikut:  N – panjangnya pesan.  M – suatu array satu dimensi berisi N bilangan bulat menyatakan pesan. Anda dapat mengasumsikan bahwa 0 ≤ M[i] ≤ 255 untuk 0 ≤ i < N. Prosedur ini harus mengubah pesan M menjadi sederetan bilangan bulat antara 0 dan R, inklusif, yang akan dikirim menggunakan burung kakatua. Untuk melaporkan deret ini, prosedur encode Anda harus memanggil prosedur send(a) untuk setiap bilangan bulat a yang Anda inginkan untuk diberikan kepada burung.  Prosedur decode(N,L,X) yang mempunyai parameter sebagai berikut:  N – panjang pesan semula.  L – panjang pesan yang diterima (banyaknya burung yang dikirim).  X – sebuah array satu dimensi yang berisi L bilangan bulat menyatakan pesan yang diterima. Bilangan X[i] untuk 0 ≤ i < L adalah angka yang persis sama dengan yang dihasilkan prosedur encode Anda, tetapi urutannya mungkin berbeda. Prosedur ini harus dapat menemukan kembali pesan semula. Untuk melaporkannya, prosedur decode Anda harus memanggil prosedur output(b) untuk setiap bilangan bulat b pada pesan yang diubah kembali, dalam urutan yang benar. Perhatikan bahwa R dan K tidak diberikan sebagai parameter input – mohon lihat deskripsi subtask di bawah.

Halaman 2 dari 6



Untuk menyelesaikan dengan benar suatu subtask yang diberikan, prosedur Anda harus memenuhi kondisi sebagai berikut:  Semua bilangan bulat yang dikirimkan oleh prosedur encode harus berada dalam rentang yang diberikan spesifikasinya pada subtask.  Banyaknya pemanggilan prosedur encode terhadap prosedur send tidak boleh melebihi batasan K yang diberikan pada subtask. Perhatikan bahwa K bergantung pada panjang pesan.  Prosedur decode harus menemukan kembali pesan semula M dan memanggil prosedur output(b) tepat sebanyak N kali, dengan b sama dengan M[0], M[1], ..., M[N-1], secara berturutan. Pada subtask terakhir, skor Anda bervariasi sesuai dengan rasio antara panjang dari pesan yang terencode dan pesan semula.

Contoh Perhatikan kasus dimana N=3, dan 10 M= 30 20 Prosedur encode(N,M), menggunakan suatu metode yang aneh, mungkin mengubah pesan menjadi deretan bilangan (7, 3, 2, 70, 15, 20, 3). Untuk melaporkan deretan ini, prosedur encode harus memanggil prosedur send sebagai berikut: send(7) send(3) send(2) send(70) send(15) send(20) send(3) Saat semua burung kakatua mencapai tujuannya, asumsikan bahwa kita memperoleh deretan bilangan bulat sebagai berikut: (3, 20, 70, 15, 2, 3, 7). Prosedur decode kemudian akan dipanggil dengan N=3, L=7, dan 3 20 70 X= 15 2 3 7

Halaman 3 dari 6



Prosedur decode harus menghasilkan pesan semula (10, 30, 20). Prosedur decode melaporkan hasil dengan memanggil prosedur output sebagai berikut. output(10) output(30) output(20)

Subtask Subtask 1 (17 poin)  N = 8, dan setiap bilangan bulat dalam array M adalah 0 atau 1.  Setiap bilangan bulat yang di-encode harus dalam rentang nilai dari 0 sampai dengan R=65535, inklusif.  Banyaknya pemanggilan maksimal yang boleh Anda lakukan untuk prosedur send adalah K=10×N.

Subtask 2 (17 poin)  1 ≤ N ≤ 16.  Setiap bilangan bulat yang di-encode harus dalam rentang nilai 0 sampai dengan R=65535, inklusif.  Banyaknya pemanggilan maksimal yang boleh Anda lakukan untuk prosedur send adalah K=10×N.

Subtask 3 (18 poin)  1 ≤ N ≤ 16.  Setiap bilangan bulat yang di-encode harus dalam rentang nilai dari 0 sampai dengan R=255, inklusif.  Banyaknya pemanggilan maksimal yang boleh Anda lakukan untuk prosedur send adalah K=10×N.

Subtask 4 (29 poin)  1 ≤ N ≤ 32.  Setiap bilangan bulat yang di-encode harus dalam rentang nilai dari 0 sampai dengan R=255, inklusif.  Banyaknya pemanggilan maksimal yang boleh Anda lakukan untuk prosedur send adalah K=10×N.

Subtask 5 (hingga 19 poin)  16 ≤ N ≤ 64.  Setiap bilangan bulat yang di-encode harus dalam rentang nilai dari 0 sampai dengan R=255, inklusif. Halaman 4 dari 6



 Banyaknya pemanggilan maksimal yang boleh Anda lakukan untuk prosedur send adalah K=15×N.  Penting: Nilai untuk subtask ini tergantung kepada rasio antara panjangnya pesan yang dienkode dan pesan semula. Untuk sejumlah t kasus dalam subtask ini, misalkan Pt=Lt/Nt adalah rasio antara panjang Lt dari pesan yang di-encode dan panjang Nt dari pesan semula. Misalkan P adalah maksimum semua nilai Pt. Skor Anda untuk subtask akan ditentukan menggunakan aturan sebagai berikut:  Jika P ≤ 5, Anda mendapat nilai penuh sebesar 19 poin.  Jika 5 < P ≤ 6, Anda mendapat 18 poin.  Jika 6 < P ≤ 7, Anda mendapat 17 poin.  Jika 7 < P ≤ 15, skor Anda adalah 1 + 2 × (15 - P), dibulatkan ke bawah ke bilangan bulat terdekat.  Jika P > 15 atau ada keluaran Anda yang tidak benar, skor Anda adalah 0. Penting: Setiap solusi valid pada subtask 1 sampai dengan 4 juga akan dapat menyelesaikan subtask pendahulunya. Namun, dengan alasan batasan K yang lebih besar, solusi valid untuk subtask 5 belum tentu dapat menyelesaikan subtask 1 sampai dengan 4. Ada solusi yang sama yang dapat menyelesaikan semua subtask.

Rincian Implementasi Batasan  Lingkungan pengujian: pada lingkungan pengujian yang sebenarnya, jawaban Anda akan dikompilasi menjadi dua program e dan d yang dieksekusi terpisah. Modul encoder dan decoder akan di-link ke setiap executable, tapi e hanya memanggil encode and d hanya memanggil decode.  Batasan waktu CPU: Program e akan memanggil procedure encode sebanyak 50 kali dan harus dapat dijalankan dalam 2 detik. Program d akan memanggil 50 kali prosedur decode dan program harus dapat dijalankan dalam 2 detik.  Batasan Memori: 256 MB Catatan: Tidak ada batasan spesifik mengenai ukuran memori stack. Memori stack diperhitungkan terhadap penggunaan memori secara keseluruhan.

Antarmuka (API)  Direktori implementasi: parrots/  Harus diimplementasi oleh kontestan:  encoder.c atau encoder.cpp atau encoder.pas  decoder.c atau decoder.cpp atau decoder.pas Catatan untuk programmer C/C++: baik pada contoh penguji dan penguji sebenarnya encoder.c[pp] dan decoder.c[pp] di-link bersama dengan penguji. Oleh karena itu, Anda harus mendeklarasikan semua variabel global di dalam setiap file sebagai static untuk Halaman 5 dari 6



mencegah variabel-variabel tersebut mengganggu variabel dari file yang lain.  Antarmuka kontestan:  encoder.h atau encoder.pas  decoder.h atau decoder.pas  Antarmuka penguji:  encoderlib.h atau encoderlib.pas  decoderlib.h atau decoderlib.pas  Contoh penguji: grader.c atau grader.cpp atau grader.pas Contoh penguji menjalankan dua putaran terpisah. Pada setiap putaran, contoh penguji memanggil encode dengan data yang diberikan, dan kemudian memanggil decode dengan keluaran prosedur encode. Pada putaran pertama, contoh penguji tidak mengubah urutan bilangan bulat pada pesan yang sudah di-encode. Pada putaran kedua, contoh penguji menukar bilangan bulat pada posisi ganjil dan genap. Penguji yang sebenarnya akan mengaplikasikan berbagai jenis permutasi pada pesan yang sudah di-encode. Anda dapat mengubah bagaimana contoh penguji mengocok data dengan memodifikasi prosedur shuffle (pada C/C++) atau Shuffle (pada Pascal) Contoh penguji juga memeriksa rentang dan panjang data yang di-encode. Pada umumnya, contoh penguji memeriksa bahwa data yang di-encode berada di antara 0 dan 65535, inklusif, dan bahwa panjangnya paling banyak adalah 10xN. Anda dapat mengubahnya dengan menyesuaikan konstanta channel_range (misalnya dari 65535 ke 255) dan max_expansion (misalnya dari 10 ke 15 atau 7).  Masukan contoh penguji: grader.in.1, grader.in.2, ... Catatan: Contoh penguji membaca data dengan format sebagai berikut:  Baris 1: N  Baris 2: sederetan N bilangan: M[0], M[1], ..., M[N-1]  Keluaran yang diharap untuk masukan penguji: grader.expect.1, grader.expect.2, … Untuk persoalan ini, masing-masing berkas seharusnya berisi tepat teks “Correct.”

Halaman 6 dari 6

PARROTS. Burung Kakatua. International Olympiad in Informatics July 2011, Pattaya City, Thailand Competition Tasks Day 2 Indonesia 1

Recommend Documents