<a style="color:#000000;" href="http://www.muhammadalvin.net" title="Go back to the front page"> Muhammad Alvin

26 November 2011

Saya mendapatkan ide soal ini dari soal ACORN untuk ACM/ICPC Asia Regional Contest 2007 Singapore. Ketika itu, USU mengirimkan dua tim untuk acara ini. Tim pertama terdiri dari saya, Alfarisi, Surya Wijaya, dan tim kedua terdiri dari Izhari Ishak Aksa, Ronny Silitonga, Jefri Umar (sebenarnya tim kami yang merupakan tim kedua ). Tim kami tidak berhasil menyelesaikan soal tersebut, sementara tim satunya berhasil. Setelah kembali ke tanah air, saya berhasil menyelesaikannya. Kegagalan ini membuat saya selalu teringat dengan soal tersebut. Pelajaran berharga memang dari pengalaman, pengalaman adalah guru terbaik. Begitu kata teman saya – Yayan – ketika saya berbagi pengalaman ini.

Alice dan Bob merupakan peneliti yang sedang melakukan percobaan mutasi gen. Alice melakukan percobaannya terhadap pohon pisang, sehingga beberapa pohon pisang dapat tumbuh dengan ketinggian yang sama dan memiliki buah di berbagai titik di sepanjang pohon tersebut. Sementara Bob melakukan percobaannya terhadap monyet, sehingga monyet tersebut dapat menyelesaikan permasalahan dengan algoritma tertentu.

Alice dan Bob tinggal bersebelahan. Rumah keduanya memiliki halaman yang hanya terpisah dinding yang cukup tinggi. Di halaman rumah itulah keduanya melakukan percobaannya. Suatu hari, seekor monyet dari halaman rumah Bob secara tidak sengaja memanjat dinding tersebut dan melihat beberapa pohon pisang yang ada di rumah Alice. Melihat banyaknya pisang yang tersebar di pohon-pohon tersebut, monyet tersebut tergoda untuk mengambilnya.

Dari atas dinding, monyet hanya bisa melompat ke salah satu pohon. Selanjutnya ia harus menuruni pohon tersebut sambil mengambil pisang yang dilewatinya. Saat menuruni pohon, ia bisa turun lurus ke bawah sejauh 1 meter atau pindah ke pohon tepat di sebelah kiri atau kanannya sambil turun sejauh 2 meter.

Tentukan berapa jumlah pisang terbanyak yang dapat diambil oleh monyet tersebut.

Sebagai contoh, Alice memiliki 3 pohon pisang dengan ketinggian 5 meter. Pohon pertama memiliki 5 pisang di ketinggian 2 meter, 15 pisang di ketinggian 4 meter, dan 5 pisang di ketinggian 5 meter. Pohon kedua memiliki 20 pisang di ketinggian 2 dan 3 meter. Pohon ketiga memiliki 15 pisang di ketinggian 4 meter. Jika digambarkan menjadi seperti berikut:

Jika monyet memilih pohon pertama lalu turun lurus ke bawah, maka ia akan memperoleh 5 + 15 + 5 = 25 pisang. Jika memilih pohon kedua lalu turun lurus ke bawah, maka ia akan memperoleh 20 + 20 = 40 pisang. Jika memilih pohon ketiga lalu turun lurus ke bawah, maka ia akan memperoleh 15 pisang.

Jika monyet memilih pohon pertama lalu turun ke ketinggian 4 meter di pohon yang sama, kemudian pindah ke pohon kedua ke ketinggian 2 meter, maka ia akan memperoleh 5 + 15 + 20 = 40 pisang.

Tetapi jika monyet memilih pohon pertama, lalu pindah ke pohon kedua ke ketinggian 3 meter, kemudian turun terus ke bawah, maka ia akan memperoleh 5 + 20 + 20 = 45 pisang. Pada test case ini, 45 pisang adalah jumlah maksimum yang dapat diambil.

Ingat: Pindah pohon berarti turun 2 meter, dan monyet hanya bisa pindah ke pohon yang berada tepat di sebelah kiri atau kananya. Sebagai contoh, jika ada empat pohon dan monyet berada di pohon kedua, maka ia bisa pindah ke pohon pertama atau ketiga, tetapi tidak bisa pindah ke pohon keempat.

Input:
Input diawali oleh T (1 <= T <=1000) yang menunjukkan jumlah test case.

Setiap test case terdiri dari beberapa baris. Baris pertama berisi dua buah bilangan bulat N dan H (1 <= N, H <= 50), di mana N merupakan banyaknya pohon pisang setinggi H meter yang terdapat di halaman Alice. N baris berikutnya berisi H buah integer (X₁ X₂ X₃ … X_H di mana 0 <= X_i <= 100) yang menunjukkan letak dan jumlah pisang di setiap pohon. Integer pertama (X₁) adalah jumlah pisang di ketinggian 1 meter, integer kedua (X₂) adalah jumlah pisang di ketinggian 2 meter, integer ketiga (X₃) adalah jumlah pisang di ketinggian 3 meter, dst.

Output:
Untik setiap test case, tampilkan jumlah maksimum pisang yang dapat diambil untuk test case tersebut.

Contoh input:
4
3 5
0 5 0 15 5
0 20 20 0 0
0 0 0 15 0
1 1
10
1 10
0 0 0 0 0 0 0 0 0 0
2 5
1 2 3 4 5
1 2 3 4 5

Contoh output:
45
10
0
15

———-

Cara penyelesaian soal ini mirip seperti soal Rute Maksimal (B). Jika pada soal tersebut, yang kita cari adalah maksimum untuk turun ke kiri atau ke kanan, maka pada soal ini yang kita cari adalah maksimum untuk:

turun lurus (1 langkah ke bawah)
turun ke kiri (2 langkah ke bawah)
turun ke kanan (2 langkah ke bawah)

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;
import java.util.Arrays;

public class H {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int nTC = sc.nextInt();
        while (nTC-- > 0) {
            int N = sc.nextInt();
            int H = sc.nextInt();

            int[][] pohon = new int[52][52]; // batasan pada soal: 1 <= N, H <= 50
            for (int i = 0; i <= N; i++) {
                Arrays.fill(pohon[i], 0);
            }

            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= H; j++) {
                    pohon[i][j] = sc.nextInt();
                }
            }

            int hasil = 0; // terbanyak di ketinggian H

            // mulai dari baris ke-2 dari bawah sampai paling atas
            for (int i = 2; i <= H; i++) {
                for (int j = 1; j <= N; j++) {
                    // cari turun yg optimmal!
                    int best = pohon[j][i] + pohon[j][i - 1]; // turun lurus
                    if (j - 1 >= 1 && i - 2 >= 1) {
                        best = Math.max(best, pohon[j][i] + pohon[j - 1][i - 2]); // turun ke kiri
                    }
                    if (j + 1 <= N && i - 2 >= 1) {
                        best = Math.max(best, pohon[j][i] + pohon[j + 1][i - 2]); // turun ke kanan
                    }

                    pohon[j][i] = best; // update!

                    if (i == H) {
                        hasil = Math.max(hasil, pohon[j][i]); // update hasil
                    }
                }
            }

            System.out.println(hasil);
        }
    }

}

Input dan output yang digunakan oleh juri bisa dilihat di sini.

———-

Untuk soal ACORN, karena time limit untuk soalnya hanya 3 detik, maka tidak bisa menggunakan looping 3 tingkat (pertama untuk mengiterasi setiap ketinggian, kedua untuk mengiterasi setiap pohon, ketiga untuk mengiterasi arah turun). Saya sudah mencoba solusi tersebut dan dinyatakan No – Time Limit Exceeded. Agar mendapatkan Yes/Accepted, harus menggunakan teknik dynamic programming, di mana kita menyimpan maksimum dari tiap-tiap ketinggian di tabel DP (ada juga yang menyebutnya tabel memo). Ini akan meng-eliminasi looping ketiga dengan cara melihat nilai maksimum untuk ketinggian tertentu ke tabel DP tersebut.

This post has no tag

Permanent link to this article: http://www.muhammadalvin.net/2011/11/artechno-festival-programming-competition-monyet-dan-pisang/

Nov 26 2011

Artechno Festival Programming Competition – Hitung Prima (G)

Categories:

26 November 2011

Soal dibuat oleh Izhari Ishak Aksa.

Diberikan sebuah deretan bilangan bulat, jumlahkan bilangan-bilangan pada deretan tersebut yang merupakan bilangan prima (bilangan yang pembaginya hanya 1 dan bilangan itu sendiri). Tentukan pada bilangan prima ke berapa pada deretan tersebut ketika hasil penjumlahannya melebihi 100. Asumsikan bahwa untuk setiap kasus, pasti akan terdapat jawaban untuk hasil penjumlahan melebihi 100.

Input:
Input diawali oleh T (1 <= T <= 1000) yakni banyaknya test case.
Untuk setiap test case, diawali bilangan bulat N yang menunjukkan banyaknya bilangan pada deretan bilangan bulat. N baris berikutnya, berisi bilangan bulat X (0 < X < 1000) yaitu bilangan bulat yang dimaksud dalam deretan tersebut.

Output:
Untuk setiap test case, tampilkan sebuah bilangan bulat yang menunjukkan bilangan prima ke berapa saat hasil penjumlahannya melebihi 100.

Contoh input:
2
6
10
7
41
32
43
17
2
9
101

Contoh output:
4
1

Catatan:
Contoh input baris ke-8 tertulis 2, seharusnya 17.

———-

Pada soal ini, diminta menjumlahkan setiap bilangan prima yang ditemukan. Saat penjumlahan tersebut menghasilkan jumlah yang lebih besar dari 100, maka hentikan penjumlahan dan tampilkan pada penjumlahan ke berapa yang menghasilkan jumlah lebih dari 100 tersebut.

Berikut ini merupakan contoh solusi menggunakan bahasa Java:

import java.util.Scanner;
import java.util.Arrays;

public class G {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        // sieve of eratosthenes
        boolean[] prima = new boolean[1002]; // batasan input: 0 < X < 1000
        Arrays.fill(prima, true);
        prima[0] = prima[1] = false;
        for (int i = 2; i * i <= 1000; i++) {
            for (int j = 2; (j * i) <= 1000; j++) {
                prima[j * i] = false;
            }
        }

        int nTC = sc.nextInt();
        while (nTC-- > 0) {
            int N = sc.nextInt();

            int[] bilangan = new int[N];
            for (int i = 0; i < N; i++) {
                bilangan[i] = sc.nextInt();
            }

            int ke = 0;
            int jumlah = 0;
            for (int i = 0; i < N; i++) {
                if (prima[bilangan[i]]) {
                    jumlah += bilangan[i];
                    ke++;

                    if (jumlah > 100) {
                        break;
                    }
                }
            }

            System.out.println(ke);
        }
    }

}

Input dan output yang digunakan oleh juri dapat dilihat di sini.

Tags: prima, sieve of eratosthenes

Permanent link to this article: http://www.muhammadalvin.net/2011/11/artechno-festival-programming-competition-hitung-prima/

Nov 26 2011

Artechno Festival Programming Competition – Lingkaran dan Persegi (F)

Categories:

26 November 2011

Ini merupakan variasi soal Porseni V Imilkom USU 2010, di mana yang diminta pada soal ini hanya luas lingkaran paling dalam, tidak semua lingkaran seperti yang diminta pada soal untuk Porseni.

Diberikan masukan S yaitu panjang sisi persegi dan N yaitu banyaknya persegi dan lingkaran, hitung luas lingkaran yang terletak paling dalam. Sebagai contoh, jika diberikan S = 10 dan N = 1, maka akan terdapat 1 persegi dan lingkaran seperti berikut:

Luas yang akan dihitung adalah bagian yang berwarna biru. Dari gambar di atas, diameter lingkaran sama dengan panjang sisi persegi, yaitu 10, sehingga luas lingkaran berwarna biru tersebut adalah 78.539816 (luas lingkaran = π r² = ¼ π d², di mana π = 3.1415926535897932).

Jika diberikan S = 10 dan N = 2, maka terdapat 2 persegi dan lingkaran seperti berikut:

Luas yang akan dihitung adalah bagian yang berwarna hijau.

Input:
Input diawali oleh T (1 <= T <= 1000) yakni banyaknya test case.
T baris berikutnya (di mana setiap baris merupakan sebuah test case) berisi dua bilangan bulat S (1 <= S <= 10000) dan N (1 <= N <= 100).

Output:
Untuk setiap test case, tampilkan luas lingkaran yang diminta (lingkaran paling dalam) dalam 6 angka desimal. Lakukan pembulatan bila perlu.

Contoh input:
3
10 1
10 2
14 4

Contoh output:
78.539816
39.269908
19.242255

———-

Untuk N = 1, akan terdapat persegi dan lingkaran sebagai berikut:

Luas yang akan dihitung adalah bagian yang berwarna biru. Dari gambar di atas, jari-jari lingkaran (R₁) adalah ½ panjang sisi persegi (S₁), yaitu 5, sehingga luas lingkaran (L) tersebut adalah sebagai berikut:

$L=\pi r^{2}$
$L=\pi 5^{2}$
$L=78.539816$

Jika N = 2, maka akan terdapat 2 buah persegi dan 2 buah lingkaran seperti berikut:

Luas yang akan dihitung adalah bagian yang berwarna hijau. Untuk itu, kita perlu mengetahui jari-jari atau diameter lingkaran berwarna hijau. Perhatikan gambar berikut:

Jari-jari lingkaran berwarna hijau adalah R₂. Selanjutnya perhatikan gambar berikut:

Dari gambar tersebut, diperoleh persamaan berikut:

$(R_{1})^{2}=(R_{2})^{2}+(R_{2})^{2}$
$(R_{1})^{2}=2((R_{2})^{2})$
$(R_{2})^{2}=\frac{1}{2}((R_{1})^{2})$
$R_{2}=\sqrt{\frac{1}{2}((R_{1})^{2})}$
$R_{2}=R_{1}\sqrt{\frac{1}{2}}$

Karena kita sudah memiliki R₁ (yaitu 5), maka R₂ bisa diperoleh:

$R_{2}=R_{1}\sqrt{\frac{1}{2}}$
$R_{2}=5\sqrt{\frac{1}{2}}$
$R_{2}=3.535534$

Sehingga luas lingkaran berwarna hijau adalah:

$L=\pi (R_{2})^{2}$
$L=\pi (3.536)^{2}$
$L=39.269908$

Untuk N selanjutnya (2, 3, 4, …), dapat diturunkan rumus yang sama:

$R_{N}=R_{N-1}\sqrt{\frac{1}{2}}$

Karena sudah memperoleh jari-jari, luas lingkaran dapat dihitung.

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;

public class F {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int nTC = sc.nextInt();
        while (nTC-- > 0) {
            int S = sc.nextInt();
            int N = sc.nextInt();

            double R = 0.5 * (double) S; // 1 persegi dan lingkaran
            for (int i = 2; i <= N; i++) {
                R = R * Math.sqrt(0.5); // 2, 3, 4, ... persegi dan lingkaran
            }

            double L = Math.PI * Math.pow(R, 2);
            System.out.println(String.format("%.6f", L));
        }
    }

}

Input dan output yang digunakan oleh juri bisa dilihat di sini.

Tags: luas lingkaran, teorema pythagoras

Permanent link to this article: http://www.muhammadalvin.net/2011/11/artechno-festival-programming-competition-lingkaran-dan-persegi/

Nov 24 2011

Artechno Festival Programming Competition – Pesan Rahasia (E)

Categories:

24 November 2011

Soal ini sudah pernah saya tulis untuk Porseni V Imilkom USU 2010. Perbedaannya ada pada output yang diminta dan test case yang lebih ‘menjebak’ .

Ada banyak cara merahasiakan pesan, salah satunya menggunakan Caesar Cipher. Teknik ini sangat sederhana, pesan rahasia diperoleh dengan menggantikan setiap huruf pada pesan asli dengan huruf yang sudah ditentukan. Huruf tersebut diperoleh dengan menggeser huruf asli sejauh N. Sebagai contoh, untuk N = 1, kita akan memiliki tabel berikut:

Huruf asli    : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Huruf rahasia : B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

Sehingga jika ada pesan asli:

ILMU KOMPUTER

akan menghasilkan pesan rahasia:

JMNV LPNQVUFS

Untuk N = 2 tentu saja hasilnya akan berbeda, yaitu:

KNOW MQORWVGT

Saat ini Anda berperan sebagai penyadap pesan. Anda diminta mencari tahu pesan asli yang tersembunyi dari pesan rahasia yang didapat dari proses menyadap tersebut. Tentu saja Anda tidak mengetahui N. Petunjuk yang dapat digunakan adalah dalam pesan asli terdapat salah satu kata ganti orang berikut:

AKU
SAYA
GUE
KAU
KAMU
ELO
DIA
KALIAN
KAMI
KITA
MEREKA

Sebagai contoh Anda mendapatkan pesan rahasia:

TBZB BMVNOJ QSPHSBN TUVEJ T1 JMNV LPNQVUFS GNJQB VTV

Maka dengan N = 1 Anda akan mendapatkan pesan asli:

SAYA ALUMNI PROGRAM STUDI S1 ILMU KOMPUTER FMIPA USU

Perhatikan bahwa di pesan asli tersebut terdapat kata SAYA. Jika Anda menggunakan N selain 1, maka tidak akan ditemukan salah satu kata ganti orang yang telah disebutkan sebelumnya.

Input:
Input diawali T (1 <= T <= 1000) yakni banyaknya test case.
T baris berikutnya (di mana setiap baris merupakan sebuah test case) terdiri dari rangkaian huruf (A-Z), angka (0-9) dan SPASI. Setiap baris tidak melebihi 100 karakter.

Output:
Untuk setiap test case, tampilkan pesan asli yang diperoleh. Jika pesan asli tidak ditemukan, tampilkan *UNKNOWN*.

Contoh input:
4
TBZB BMVNOJ QSPHSBN TUVEJ T1 JMNV LPNQVUFS GNJQB VTV
UCAC CNWOPK RTQITCO UVWFK U1 KNOW MQORWVGT HOKRC WUW
LDMTQTS RZXZ JQHOSNFQZEH LDQTOZJZM LZSZ JTKHZG XZMF LDMXDMZMFJZM
ZZZZZ

Contoh output:
SAYA ALUMNI PROGRAM STUDI S1 ILMU KOMPUTER FMIPA USU
SAYA ALUMNI PROGRAM STUDI S1 ILMU KOMPUTER FMIPA USU
MENURUT SAYA KRIPTOGRAFI MERUPAKAN MATA KULIAH YANG MENYENANGKAN
*UNKNOWN*

Catatan:
Pada soal yang dibagikan juri, terdapat tanda koma pada contoh input baris ke-4 setelah RZXZ. Begitu juga dengan contoh output pada baris ke-4 setelah SAYA. Ini merupakan suatu kesalahan pada soal yang dibagikan.

———-

Pada contoh tabel yang disebutkan di soal, karakter yang digeser hanya huruf (A-Z). Jumlah karakter tersebut adalah 26. Artinya, pergeseran yang mungkin dilakukan mulai dari 0 sampai dengan 25. Pergeseran 26 huruf akan kembali seperti pergeseran 0 huruf, pergeseran 27 huruf akan kembali seperti pergeseran 1 huruf, dst.

Kemudian, hati-hati saat memeriksa apakah kata yang dimaksud terdapat dalam pesan asli. Kata merupakan sesuatu yang dipisah oleh tanda baca (dalam hal ini adalah SPASI). Sebagai contoh, kata SAYA terdapat dalam kalimat “SAYA ALUMNI ILKOM”, tetapi tidak pada kalimat “ABC DSAYAE FGH”. Namun substring SAYA terdapat pada kedua kalimat tersebut.

Hal lain yang perlu diperhatikan adalah apabila pesan asli dapat diperoleh untuk beberapa nilai N. Misalnya pesan rahasia berikut:

TBZB EBO NDPX

Saat menggunakan N = 1 akan diperoleh:

SAYA DAN MCOW

Karena ada kata SAYA, maka pesan di atas dapat dianggap sebagai pesan asli.

Selanjutnya, saat menggunakan N = 2 akan diperoleh:

RZXZ CZM LBNV

Kemudian, saat menggunakan N = 3 akan diperoleh:

QYWY BYL KAMU

Karena ada kata KAMU, maka pesan di atas juga dapat dianggap sebagai pesan asli. Untuk kasus seperti ini, kita tidak tahu pesan asli mana yang benar, apakah yang ini atau yang sebelumnya. Jadi untuk kasus ini kita juga harus menampilkan *UNKNOWN*

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;

public class E {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int nTC = sc.nextInt();

        // sc.nextLine() untuk melewatkan '\n' di akhir baris ini
        sc.nextLine();

        while (nTC-- > 0) {
            String pesan = sc.nextLine();
            int len = pesan.length();

            String hasil = "";

            // coba 0 - 25 pergeseran
            for (int shift = 0; shift <= 25; shift++) {
                StringBuilder asli = new StringBuilder(len);
                for (int i = 0; i < len; i++) {
                    char c = pesan.charAt(i);
                    if (c >= 'A' && c <= 'Z') {
                        int p = ((int) c - 'A' + shift) % 26;
                        asli.append((char) (p + 'A'));
                    } else {
                        asli.append(c);
                    }
                }

                // periksa apakah terdapat kata dalam kamus
                String tmp = " " + asli.toString() + " ";
                if (tmp.indexOf(" AKU ") != -1 || tmp.indexOf(" SAYA ") != -1 ||
                    tmp.indexOf(" GUE ") != -1 || tmp.indexOf(" KAU ") != -1 ||
                    tmp.indexOf(" KAMU ") != -1 || tmp.indexOf(" ELO ") != -1 ||
                    tmp.indexOf(" DIA ") != -1 || tmp.indexOf(" KALIAN ") != -1 ||
                    tmp.indexOf(" KAMI ") != -1 || tmp.indexOf(" KITA ") != -1 ||
                    tmp.indexOf(" MEREKA ") != -1) {

                    // kalo sebelumnya sudah ditemukan pesan asli, dan sekarang
                    // ditemukan lagi pesan asli lain, maka itu berarti ambigu.
                    if (hasil.compareTo("") == 0) {
                        hasil = asli.toString();
                    } else {
                        hasil = "*UNKNOWN*";
                        break;
                    }
                }
            }

            // pesan asli tidak berhasi diperoleh.
            if (hasil.compareTo("") == 0) {
                hasil = "*UNKNOWN*";
            }

            System.out.println(hasil);
        }
    }

}

Input dan output yang digunakan oleh juri bisa dilihat di sini.

This post has no tag

Permanent link to this article: http://www.muhammadalvin.net/2011/11/artechno-festival-programming-competition-pesan-rahasia/

Nov 23 2011

Artechno Festival Programming Competition – Bilangan Bulat (D)

Categories:

23 November 2011

Sebenarnya, ide soal ini berasal dari binary search. Saya ingin membuat soal di mana peserta harus mencari suatu nilai dari sekumpulan data yang cukup banyak, yang tidak boleh dilakukan secara sekuensial karena akan memakan waktu.

Diberikan sebuah bilangan desimal, tentukan 2 buah bilangan:

X, bilangan bulat terbesar yang lebih kecil dari bilangan desimal tersebut
Y, bilangan bulat terkecil yang lebih besar dari bilangan desimal tersebut

Sebagai contoh, jika diberikan bilangan desimal 3.14, maka nilai X dan Y adalah 3 dan 4.

Input:
Input diawali oleh bilangan bulat T (1 <= T <= 1000) yakni banyaknya test case.
T baris berikutnya (dimana setiap baris merupakan sebuah test case) terdiri dari sebuah bilangan desimal N (-10⁹ <= N <= 10⁹). Bilangan desimal ini memiliki maksimum 3 angka desimal.

Output:
Untuk setiap test case, tampilkan dua buah bilangan bulat yang diminta (X dan Y) dengan dipisahkan oleh sebuah spasi.

Contoh input:
2
3.14
123456.789

Contoh output:
3 4
123456 123457

———-

Seperti yang saya katakan di awal, soal ini tentang pencarian (binary search). Saya sempat berpikir mungkin akan ada peserta yang mensubmit jawaban ini dengan menggunakan for (i = -1000000000; i <= 1000000000; i++). Tentunya cara tersebut bukanlah sebuah solusi, mengingat ada maksimum 1000 test case. Ini artinya program akan melakukan looping dua tingkat, di mana tingkat pertama ada 1000 iterasi dan tingkat kedua ada 2 milyar iterasi dalam kondisi terburuk (worst case).

Namun karena data yang 2 milyar itu terurut, mestinya binary search bisa diterapkan. Tetapi saya sendiri belum mencoba menyelesaikannya menggunakan binary search.

Dalam setiap bahasa pemrograman, ada fungsi matematika floor() dan ceil(). Fungsi floor(N) mengembalikan nilai bilangan bulat terbesar yang tidak lebih besar dari N. Fungsi ceil(N) mengembalikan nilai bilangan bulat terkecil yang tidak lebih kecil dari N.

Contoh:

floor(1.99) = 1, karena 1 merupakan bilangan bulat terbesar yang tidak lebih besar dari 1.99
floor(-3.14) = -4, karena -4 merupakan bilangan bulat terbesar yang tidak lebih besar dari -3.14
ceil(5.07) = 6, karena 6 merupakan bilangan bulat terkecil yang tidak lebih kecil dari 5.07
ceil(-7.11) = -7, karena -7 merupakan bilangan bulat terkecil yang tidak lebih kecil dari -7.11
floor(5.0) = 5, karena 5 merupakan bilangan bulat terbesar yang tidak lebih besar dari 5.0 (5 sama dengan 5.0)
ceil (-8.0) = -8, karena -8 merupakan bilangan bulat terkecil yang tidak lebih kecil dari -8.0 (-8 sama dengan 8.0)

Submission yang diterima judge banyak yang terjebak dengan 2 contoh terakhir. Soal ini meminta bilangan bulat terbesar yang lebih kecil dari bilangan desimal pada input dan bilangan bulat terkecil yang lebih besar dari bilangan desimal pada input.

Jika bilangan desimal adalah 9.0, maka X = 9 adalah salah (karena 9 tidak lebih kecil dari 9.0). X yang benar adalah 8. Begitu juga dengan Y (bukan 9 tetapi 10).

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;

public class D {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int nTC = sc.nextInt();
        while (nTC-- > 0) {
            double N = sc.nextDouble();

            double X = Math.floor(N);
            double Y = Math.ceil(N);

            // karena X harus lebih kecil dari N, maka untuk X == N (dalam 3 desimal,
            // seperti yang dijelaskan pada soal), X harus dikurangi 1.
            if (String.format("%.3f", X).compareTo(String.format("%.3f", N)) == 0) {
                X--;
            }

            // begitu juga dengan Y yang harus lebih besar dari N.
            if (String.format("%.3f", Y).compareTo(String.format("%.3f", N)) == 0) {
                Y++;
            }

            System.out.println((int) X + " " + (int) Y);
        }
    }

}

Input dan output yang digunakan juri dapat dilihat di sini.

Tags: ceil, floor