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

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

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

Nov 23 2011

Artechno Festival Programming Competition – Tahun Kabisat (C)

Categories:

23 November 2011

Soal ini sudah pernah saya tulis untuk Porseni VI Imilkom USU 2011. Perbedaannya hanyalah pada output yang diminta.

Diberikan tahun dan interval, tampilkan tahun tersebut beserta tahun-tahun sebelum dan sesudahnya. Untuk tahun yang merupakan tahuun kabisat, tandai dengan tanda bintang/asterisk (*).

Sebagai contoh, diberikan tahun 2011 dan interval 3. Maka tampilkan tahun tersebut (2011) dan 3 tahun setelahnya (2012, 2013, 2014):

2011
2012 *
2013
2014

Jika interval merupakan bilangan negatif, tampilkan tahun-tahun sebelumnya. Sebagai contoh diberikan tahun 2011 dan interval -3, maka:

2011
2010
2009
2008 *

Input:
Input diawali oleh bilangan bulat T (1 <= T <= 1000) yakni banyaknya test case.
T baris berikutnya (di mana setiap baris adalah sebuah test case), terdiri dari dua bilangan bulat Y (1000 <= Y <= 9999) yang merupakan tahun dan N (-1000 <= N <= 1000) yang merupakan interval.

Output:
Untuk setiap test case, tampilkan ‘#’ yang diikuti oleh nomor urut test case (1, 2, 3, …). Selanjutnya tampilkan tahun pada input (Y), tahun-tahun sebelum/setelahnya, serta keterangan kabisat berupa tanda bintang/asterisk (*) untuk tahun yang merupakan tahun kabisat.

Contoh input:
3
2011 3
2011 -3
2011 0

Contoh output:
#1
2011
2012 *
2013
2014
#2
2011
2010
2009
2008 *
#3
2011

———-

Pada soal ini, banyak peserta yang terjebak dengan definisi tahun kabisat. Banyak submission yang diterima judge hanya menyertakan pengujian if (tahun % 4 == 0) untuk pengujian tahun kabisat.

Definisi tahun kabisat yang benar adalah:

Jika tahun HABIS dibagi 100, maka tahun tersebut HARUS habis dibagi 400.

Atau…

Jika tahun TIDAK HABIS dibagi 100, maka tahun tersebut HARUS habis dibagi 4.

Berikut ini merupakan contoh solusi dalam bahasa Java:

import java.util.Scanner;

public class C {

    private static boolean isKabisat(int tahun)
    {
        if (tahun % 100 == 0) {
            return (tahun % 400 == 0);
        } else {
            return (tahun % 4 == 0);
        }
    }

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

        int no = 0;

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

            System.out.println("#" + ++no);
            System.out.println(Y + (isKabisat(Y) ? " *" : ""));

            if (N > 0) {
                for (int i = 1; i <= N; i++) {
                    int tahun = Y + i;
                    System.out.println(tahun + (isKabisat(tahun) ? " *" : ""));
                }
            } else {
                N = Math.abs(N);
                for (int i = 1; i <= N; i++) {
                    int tahun = Y - i;
                    System.out.println(tahun + (isKabisat(tahun) ? " *" : ""));
                }
            }
        }
    }

}

Input dan output yang digunakan juri dapat dilihat di sini.

Tags: kabisat

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

Nov 22 2011

Artechno Festival Programming Competition – Rute Maksimal (B)

Categories: