Tantangan Anda:
Anda berada di lantai 0 sebuah gedung tinggi tanpa batas. Di lantai mana pun, Anda bisa berjalan ke jendela dan menjatuhkan sebutir telur. Tujuan Anda adalah untuk mengetahui lantai tertinggi yang dapat ditahan telur tanpa pecah. Namun, Anda memiliki maksimal 3 butir telur untuk digunakan, tetapi Anda harus meminimalkan jumlah percobaan.
Secara formal:
- Anda diberi fungsi
f(n)
yang mengembalikanbool(n <= X)
untuk sesuatu yang tidak dikenalX
, di mana0 <= X
- Anda harus mengembalikan nilai
X
(tanpa mengaksesnya langsung) f(n)
harus hanya mengembalikanFalse
waktu maksimum3
(dalam satu test case). Jika kembaliFalse
lebih dari itu, maka jawaban Anda didiskualifikasi.
Batasan
Skor Anda adalah jumlah total panggilan yang Anda lakukan f(n)
(dalam kasus uji di bawah)
Jika mau, Anda dapat mengabaikan fungsi, dan hanya "mensimulasikan" situasi di atas. Namun , algoritma pemecahan Anda harus tahu apa-apa X
.
Algoritme Anda seharusnya tidak memberikan kode pada kasus pengujian, atau maksimum X
. Jika saya ingin membuat ulang angka, atau menambahkan lebih banyak, program Anda harus dapat menanganinya (dengan skor yang sama).
Jika bahasa Anda tidak mendukung integer presisi sewenang-wenang, maka Anda dapat menggunakan long
tipe data. Jika bahasa Anda tidak mendukung, maka Anda kurang beruntung.
Kasing uji n dihasilkan menggunakan yang berikut ini:
g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0
, atau sekitar 1.25^n
Kasus uji:
0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509
Ini adalah tantangan kode , dan orang dengan skor terendah menang!
sumber
Jawaban:
Javascript,
44285944285774825 panggilanTes di sini
Skor untuk setiap kasus uji individual:
Bagaimana itu bekerja:
1 butir telur:
Ketika ada satu telur, strategi terbaik adalah naik 1 lantai pada satu waktu dan mengembalikan lantai tepat di bawah lantai di mana ia pecah terlebih dahulu.
2 telur:
Ketika kita memiliki dua telur, jumlah lantai maksimum yang harus kita periksa akan menjadi n terkecil dimana T n lebih besar dari kisaran lantai yang harus kita periksa. T n adalah angka segitiga ke-n. Lemparan pertama akan dilakukan di lantai ke-n. Lemparan kedua akan dilakukan
n - 1
lantai di atas lemparan pertama. Lemparan ke-11 akan dilakukan din - m + 1
atasm - 1
lemparan ke-10. Setelah telur pecah, dibutuhkann - m
lemparan untuk menentukan lantai dengan metode pertama.3 telur:
Dengan telur pertama kita, kita harus menentukan batas atas untuk lantai tertinggi. Awalnya, saya melakukan ini dengan menggandakan nomor lantai setiap kali. Setelah menganalisis algoritma untuk 2 telur saya pikir mungkin akan lebih baik jika setiap kali kita melempar telur, max melempar untuk menemukan lantai yang benar dengan 2 telur akan meningkat 1. Ini dapat dipenuhi dengan menggunakan angka tetrahedral. Setelah telur pertama pecah, kita dapat menggunakan metode di atas untuk sisa telur kita.
Tetesan telur maks yang dibutuhkan untuk menentukan lantai harus optimal. Namun, algoritma yang lebih baik mungkin dapat ditemukan di mana rata-rata tetesan telur lebih baik.
sumber
Java, 68985 panggilan
Hasil tes:
Program uji:
Sambil mengoptimalkan saya bertujuan untuk mencoba membuat jumlah upaya dengan masing-masing telur kira-kira sama.
sumber
Ruby,
6746666026 panggilanKode uji:
Hasil:
Algoritma ini berfungsi seperti algoritma lama saya, tetapi memiliki beberapa perbedaan:
Tetesan telur pertama ada di lantai 8
Kenaikan pertama adalah 8 * 8 = 64
Angka-angka ini adalah hasil dari fine tuning acak dengan tangan.
sumber