Archive for ACM Contest

Factorial Factors Versi C

ACM-884Saya masih penasaran dengan soal nomor 884 Factorial Factors di UVA Online Judge. Artikel di blog ini membahas soal tersebut pada 2006. Hasil terbaik (setelah Online Judge pindah tempat) pada 21 Agustus 2011 di urutan 3, dengan waktu 0.044 detik. Masalahnya, peringkat pertama hanya membutuhkan waktu 0.020 detik atau 2x lebih cepat. Baca entri selengkapnya »

Iklan

Tinggalkan sebuah Komentar

Problem 871: Counting Cells in a Blob

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.

Baca entri selengkapnya »

Comments (1)

Problem 893: Y3K Problem

Pemecahan soal ini tergolong mudah, yaitu copy + paste dari unit SysUtils di Delphi. Sebenarnya tidak sulit untuk mengerjakan sendiri, tetapi godaan untuk tidak mencontek sangat besar, dan saya memilih menyerah dengan godaan itu. Penyesuaian tetap perlu diadakan, mengingat TDateTime di Delphi adalah bertipe Double sedangkan Integer sudah mencukupi. Termasuk pula pengecekan apakah cakupan hari, bulan dan tahun tidak melewati batas, yang bisa ditiadakan di soal ini.

Baca entri selengkapnya »

Tinggalkan sebuah Komentar

Problem 872: Ordering

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.

Baca entri selengkapnya »

Tinggalkan sebuah Komentar

Lingkaran Warna

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: Baca entri selengkapnya »

Comments (2)

Mempercepat Operasi I/O Teks FreePascal

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.

Baca entri selengkapnya »

Tinggalkan sebuah Komentar

Factorial Factors

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. Baca entri selengkapnya »

Comments (1)