Problem 871: Counting Cells in a Blob

March 15, 2009 at 2:18 am | Posted in ACM Contest | 1 Comment
Tags: ,

Oleh: Mpu Gondrong

blob pada grid Pada soal ini ditanyakan berapa ukuran dari blob yang terbesar dari sekumpulan blob yang diberikan. Bila diibaratkan papan catur, grid di sini adalah keseluruhan kotak berwarna putih sebagai dasar dan blob adalah sekumpulan kotak-kotak berwarna hitam. Secara mudah grid dapat disusun menggunakan array of string dengan penanda kotak hitam adalah karakter ‘1’. Menghitung ukuran terbesar blob dengan menyusuri kotak-kotak hitam ke arah kiri, kanan, atas, bawah dan diagonal secara rekursif, menghitung berapa banyaknya hingga terbentur dengan kotak putih.

Continue Reading Problem 871: Counting Cells in a Blob…

Advertisements

Problem 872: Ordering

March 14, 2009 at 10:56 pm | Posted in ACM Contest | Leave a comment
Tags:

Oleh: Mpu Gondrong

Berikut ini adalah pemecahan dari soal 872 tentang Ordering (penyusunan). Silakan ditelaah dengan baik soalnya dan contoh input / output. Sebagai sesama programmer bahasa program tentu lebih mudah dimengerti ketimbang bahasa manusia. Saya sendiri sudah lupa dan malas mengingat bagaimana membaca program di bawah, meskipun buatan sendiri. Selamat membaca.

Continue Reading Problem 872: Ordering…

Lingkaran Warna

October 30, 2006 at 5:23 pm | Posted in ACM Contest, Algorithms | 8 Comments

By: Mpu Gondrong

Kali ini kita membahas soal di http://acm.uva.es/p/v8/899.html tentang permainan menggunakan lingkaran berwarna. Di sini bermain 2 orang yang saling bergantian berpindah arah. Tujuannya sederhana, yaitu mencapai lingkaran tujuan dengan pergerakan minimal.

Meskipun soal ini tampak biasa-biasa saja, tapi cukup baik sebagai contoh penggunaan fungsi / prosedur rekursif. Rekursif berarti memanggil dirinya sendiri. Pada banyak bahasa pemrograman kemampuan untuk rekursif ini sangat membantu dalam menyederhanakan logika program.

Dari soal yang disajikan kurang lebih ada aturan berikut:

  • Terdapat lingkaran dari 1 s/d 100.
  • Tiap lingkaran memiliki warna dan dimungkinkan terdapat duplikasi.
  • Terdapat panah-panah yang menghubungkan dari satu lingkaran ke lingkaran yang lain. Panah tersebut berisi data: dari, ke, dan warna.

Dalam melakukan pergerakan terdapat aturan berikut:

Continue Reading Lingkaran Warna…

Mempercepat Operasi Input / Output Teks di FreePascal

March 29, 2006 at 8:31 pm | Posted in ACM Contest, Code Samples | 12 Comments

By: Mpu Gondrong

Penjurian program dalam kontes ACM sepenuhnya menggunakan mesin. Secara sederhana setiap program yang dikirim akan diuji dengan serangkaian input untuk kemudian dicek apakah output yang dihasilkan sudah sesuai. Penyusunan peringkat program terbaik didasarkan pada waktu eksekusi yang tercepat. Secara teknis program penjurian menggunakan NetJudge, berjalan di atas Linux, menggunakan prosesor Pentium III dan memory 1024 MByte.

Mengingat pentingnya waktu dalam penjurian, kita akan melihat bagaimana sebenarnya unjuk kerja dari Free Pascal dalam menangani teks. Dalam uji coba digunakan prosesor Intel Pentium 4 2,80GHz dan memory 2048 MByte. Sedangkan untuk file teks yang digunakan berupa angka ganjil antara 1 s/d 999999 (500.000 baris). Untuk mengukur waktu program berjalan digunakan time yang tersedia di kebanyakan Linux.

Dalam Free Pascal untuk membaca Input dan Output cukup menggunakan Readln dan Writeln. Ketika program dijalankan sistem operasi akan mengaktifkan 3 file descriptor, yaitu Input, Output dan Error yang masing-masing bernilai 0, 1 dan 2. Dengan fasilitas pengalihan tujuan (redirector) maka input, output, dan error ini bisa diarahkan dari / ke file, misalnya <input atau >output.

Continue Reading Mempercepat Operasi Input / Output Teks di FreePascal…

Factorial Factors

March 28, 2006 at 5:29 pm | Posted in ACM Contest, Code Samples | 15 Comments

by: Mpu Gondrong

Pada kesempatan kali ini kita akan membahas soal ACM vol 8 no. 884 yaitu Factorial Factors. Tujuan dari soal ini adalah kita mencari berapakah jumlah maksimal faktor pembentuk dari angka yang ditentukan.

Dari ilustrasi pada soal:

8! = 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 
   = 2 . 3 . 2 . 2 . 5 . 3 . 2 . 7 . 2 . 2 . 2 
   = jumlah 11.

Soal ini cukup menarik karena rentang waktu hasil program cukup bervariasi dan cakupan angka yang terlibat cukup besar (1 juta). Bila penghitungan waktu terlalu rapat, atau bahkan 0:00:00, kontes menjadi tidak menarik karena siapa yang mengerjakan duluan maka dialah yang menempati peringkat atas.

Awalnya

Lewat oret-oretan sederhana di kertas, kita mendapatkan suatu pola, yaitu dari suatu bilangan kita bagi saja bilangan tersebut dengan bil prima hingga tidak bisa dibagi lagi alias berakhir dgn bil prima. Jumlah banyaknya pembagian itu adalah jumlah maksimal faktor pembentuk angka tersebut.

Continue Reading Factorial Factors…

Create a free website or blog at WordPress.com.
Entries and comments feeds.