Olimpiade Sains Nasional (OSN) 2014 - Komputer, Nomor 4

1s, 32MB

Kwek dan Kwak, seperti layaknya bebek lain sedang seru-serunya bermain permainan “Rocket Duck”. Pada Rocket Duck, pemain menjalankan seekor bebek bernama “Rocky” yang ingin mencari arti hidup, yang diyakini berada diujung belahan dunia. Di luar dugaan, Rocky mencari arti hidup dengan cara yang tidak biasa dan ironis: melempar dirinya sejauh mungkin dengan alat pelontar (dan berharap mencapai ujung belahan dunia). Tentu ini cara yang ekstrim dan berbahaya. Tapi siapa peduli, Rocky hanyalah sebuah tokoh imaginer dalam sebuah game, yang terpenting bahwa permainan ini berhasil memikat banyak bebek muda.

Semua bebek ambisius mengejar high-score di Rocket Duck, begitu pula Kwek dan Kwak. Mereka membayangkan namanya terpampang pada tabel leaderboard, yang menjadi sebuah kepuasan tersendiri bagi mereka. Namun Kwek dan Kwak punya kehidupan lain, mereka tidak bisa terus menerus bermain Rocket Duck. Sehingga kemampuan mereka tidak sejago pemain lainnya. Untungnya Kwek dan Kwak kenal dengan Anda, sang programmer handal yang konon dapat menyelesaikan berbagai masalah hanya dengan hentakan jari-jemari di atas keyboard. Kini mereka memerlukan bantuan kalian untuk mengejar high-score pada permainan Rocket Duck.

Rocket Duck adalah permainan 2D, di mana pemain berusaha mencapai jarak terjauh dengan menggunakan alat pelontar bebek. Alat ini dapat melontarkan bebek pada derajat dan kecepatan awal tertentu. Bebek kemudian bergerak secara parabola, hingga akhirnya jatuh ke tanah. Nilai yang didapat dari pemain adalah jarak yang dicapai. Makin jauh jarak yang dicapai, makin tinggi nilai yang didapat. Mekanisme lontaran roket mengikuti mekanisme dasar gerak parabolik. Berikut ini adalah ilustrasi mekanisme dari gerak parabolik:

Untuk Pemain, akan disediakan beberapa pilihan roda gigi untuk merakit pelontar bebek. Setiap roda gigi memiliki dua properti, yaitu nilai kecepatan K dan nilai sudut S. Sebuah pelontar bebek nantinya akan terdiri dari beberapa roda gigi yang terpasang pada mesin. Sudut akhir dari mesin pelontar ini adalah total nilai sudut dari semua roda gigi yang dipasang. Kecepatan dari mesin pelontar ini adalah kecepatan maksimum dari semua roda gigi yang dipasang.

Sebagai tambahan, mesin pelontar ini tidak bisa menembak dengan sudut yang lebih besar dari 180 derajat. Artinya konfigurasi mesin yang menyebabkan hal tersebut terjadi tidak diperbolehkan. Perlu diperhatikan pula bahwa nilai pemain didapat dari jauhnya jarak. Artinya arah tembak dapat diabaikan (sudut kurang dari 90 derajat memiliki arah tembak berlawanan dengan sudut lebih dari 90 derajat). Jumlah roda gigi yang ada bersifat terbatas, artinya pemain hanya dapat memakai tiap roda gigi maksimal sekali saja.

Untuk membantu, berikut adalah rumus untuk menghitung jarak tembak X pada permainan Rocket Duck, diberikan nilai sudut a dan kecepatan awal V0.

Bantulah Kwek dan Kwak memilih konfigurasi roda gigi optimal, untuk mendapatkan jarak terjauh.

Format Masukan

Pada baris pertama, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, atau berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua adalah bilangan N yang menyatakan banyaknya pilihan roda gigi yang tersedia.

N baris berikutnya terdiri dari dua angka Ki dan Si, yang menyatakan nilai kecepatan dan nilai sudut dari roda gigi yang bersesuaian. Nilai sudut diberikan dengan skala perbesaran 10× lipat sehingga nilai sudut 900 maksudnya adalah 90 derajat, nilai sudut 135 maksudnya adalah 13,5 derajat, dan sebagainya.

Format Keluaran

Untuk tiap kasus uji, keluarkan sebuah bilangan riil hingga 12 angka di belakang penanda desimal yang menyatakan jarak terjauh yang dapat dicapai dengan konfigurasi roda gigi optimal. Perbedaan perhitungan absolut atau perhitungan relatif di bawah 0,001 akan diterima.

Contoh Masukan

0..3.567
3
50 160
105 320
101 290
Contoh Keluaran

107453.118185065090

Subsoal

Pada semua subsoal, berlaku:

• 1 ? S_i ? 1.800
• K_i dan S_i adalah bilangan bulat.

Subsoal 1 (8 poin)

• N = 5
• 1 ? K_i ? 100
• Nilai K tiap roda gigi adalah sama.
• Kasus uji dapat diunduh di sini.

Subsoal 2 (10 poin)

• N = 5
• 1 ? K_i ? 100
• Kasus uji dapat diunduh di sini.

Subsoal 3 (13 poin)

• 1 ? N ? 10
• 1 ? K_i ? 100

Subsoal 4 (14 poin)

• 1 ? N ? 50
• 1 ? K_i ? 100
• Nilai K tiap roda gigi adalah sama.

Subsoal 5 (15 poin)

• 1 ? N ? 50
• 1 ? K_i ? 100

Subsoal 6 (19 poin)

• 1 ? N ? 1.000
• 1 ? K_i ? 1.000

Subsoal 7 (21 poin)

• 1 ? N ? 500.000
• 1 ? K_i ? 1.000