Archive for Februari 2014
Magic Square
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Magic Square adalah persegi yang terdiri atas N x N petak, masing-masing petak berisi sebuah bilangan bulat antara 1 hingga N2 tanpa ada 2 petak yang berisi angka yang sama, di mana jumlah bilangan yang ada pada setiap baris = jumlah bilangan yang ada pada setiap kolom = jumlah bilangan yang terletak pada setiap diagonal utama. Yang dimaksud dengan diagonal utama di sini adalah diagonal yang membentang dari pojok kiri atas hingga ke pojok kanan bawah, dan diagonal yang membentang dari pojok kanan atas hingga pojok kiri bawah persegi. Tentu saja sebuah Magic Square berukuran setidaknya 3 x 3 memiliki tepat dua buah diagonal utama.
Pak Dengklek memberikan Anda beberapa pertanyaan yang masing-masing diwakilkan dengan sebuah bilangan bulat N (3 ≤ N ≤ 1.000.000). Untuk setiap bilangan bulat N yang ditanyakan, tentukan jumlah bilangan pada baris pertama magic square berukuran N x N.
Format Masukan
Baris pertama berisi bilangan bulat T (1 ≤ T ≤ 100.000) yaitu banyaknya pertanyaan Pak Dengklek. Sebanyak T baris berikutnya masing-masing berisi sebuah bilangan bulat N, yang mewakili pertanyaan Pak Dengklek.
Format Keluaran
Sebanyak T baris, masing-masing berisi sebuah bilangan bulat yang merupakan nilai K untuk setiap N yang ditanyakan, sesuai dengan urutan pada masukan.
Contoh Masukan
2 3 4
Contoh Keluaran
15 34
Penyelesaian
Penjumlahan Pecahan
| Batas Waktu | 1 detik |
| Batas Memori | 16 MB |
Pak Dengklek memberikan Anda dua buah pecahan dalam bentuk A/B dan C/D. Hitunglah A/B + C/D, lalu cetak hasilnya dalam bentuk yang paling sederhana. Bentuk paling sederhana dari suatu pecahan adalah ketika FPB dari pembilang dan penyebutnya adalah 1.
A, B, C, dan D adalah bilangan bulat positif yang muat dalam tipe data bilangan bulat 64-bit (int64 pada Free Pascal).
Format Masukan
Baris pertama berisi dua buah bilangan bulat A dan B. Baris kedua berisi dua buah bilangan bulat C dan D.
Format Keluaran
Sebuah baris berisi dua buah bilangan bulat, yaitu E dan F, di mana E/F = A/B + C/D dan E/F adalah bentuk yang paling sederhana. Dijamin E dan F muat dalam tipe data bilangan bulat 64-bit (int64 pada Free Pascal).
Contoh Masukan 1
2 3 4 5
Contoh Keluaran 1
22 15
Contoh Masukan 2
2 4 3 8
Contoh Keluaran 2
7 8
Penyelesaian
Prima Ke-K
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Pak Dengklek memberikan Anda T (1 ≤ T ≤ 20.000) buah pertanyaan. Setiap pertanyaan berbunyi, "apakah bilangan prima yang ke-K (1 ≤ K ≤ 77777)?"
Jawablah pertanyaan-pertanyaan tersebut.
Format Masukan
Baris pertama berisi sebuah bilangan bulat T. T baris berikutnya masing-masing berisi sebuah bilangan bulat K.
Format Keluaran
T buah baris, masing-masing berisi bilangan prima ke-K.
Contoh Masukan
4 1 3 5 2
Contoh Keluaran
2 5 11 3
Pembahasan
Sub-Persegi
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Suatu hari, putra Pak Dengklek pulang dari sekolah dengan sebuah pertanyaan sederhana. Ada berapa subpersegi, termasuk persegi itu sendiri, yang terdapat pada sebuah petak berukuran N x N (1 ≤ N ≤ 100)?
Format Masukan
Baris pertama berisi sebuah bilangan bulat N.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu jumlah yang dimaksud.
Contoh Masukan 1
2
Contoh Keluaran 1
5
Contoh Masukan 2
8
Contoh Keluaran 2
204
Pembahasan
Faktor Persekutuan Terbesar
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
FPB (Faktor Persekutuan Terbesar) dari dua buah bilangan bulat A dan B adalah bilangan bulat non-negatif terbesar yang membagi A dan membagi B. Misalnya, FPB dari 12 dan 20 adalah 4.
FPB dari dua buah bilangan dapat dicari secara manual. Namun, ada cara yang lebih efisien yaitu menggunakan definisi rekursif sebagai berikut (disebut Algoritma Euclid):
- FPB dari 0 dan suatu bilangan sembarang adalah bilangan sembarang tersebut.
- FPB dari A dan B sama dengan FPB dari B dan (A mod B).
Gunakan definisi rekursif ini untuk membuat sebuah fungsi rekursif yang efisien untuk menghitung FPB dari dua buah bilangan, dan pakailah di dalam program Anda.
Pak Dengklek memberikan Anda T (1 ≤ T ≤ 10.000) pasang bilangan bulat A dan B (0 ≤ A, B ≤ 1.000.000.000). Tentukan FPB dari setiap pasang A dan B tersebut.
Format Masukan
Baris pertama sebuah bilangan bulat T. T baris berikutnya masing-masing berisi dua buah bilangan bulat A dan B.
Format Keluaran
T buah baris, masing-masing berisi sebuah bilangan bulat yaitu FPB dari A dan B.
Contoh Masukan
2 12 20 1 2
Contoh Keluaran
4 1
Pembahasan
Faktorisasi Prima
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
Setiap bilangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian dari sejumlah bilangan prima. Tepatnya, setiap bulangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian dari pemangkatan sejumlah bilangan prima. Misalnya, 7 = 7, 20 = 22 x 5, dan 75 = 3 x 52.
Pak Dengklek memberikan Anda sebuah bilangan bulat N (1 ≤ N ≤ 1.000.000). Tentukan bilangan-bilangan prima a1, a2, ..., ak dan pangkat-pangkatnya, b1, b2, ..., bk, sehingga N = a1^b1 x a2^b2 x ... x ak^bk.
Format Masukan
Baris pertama berisi sebuah bilangan bulat N.
Format Keluaran
Sebuah baris berisi faktorisasi prima dari N dengan format a1^b1 x a2^b2 x ... x ak^bk. Bilangan prima a1, a2, ..., ak harus terurut dari kecil ke besar. Tanda pangkat diwakili dengan tanda '^' tanpa spasi, dan tanda kali diwakili oleh huruf 'x' kecil, diawali dan diikuti oleh sebuah spasi. Jika suatu pangkat bernilai 1, cukup ditulis faktornya saja.
Contoh Masukan 1
75
Contoh Keluaran 1
3 x 5^2
Pembahasan
Sebelumnya minta maaf kalo pembahasannya terlalu panjang, soal indentasi dan yg lain jg masih acak-acakan, sori banget yaa ~
