Meskipun mirip dengan puzzle pembawa air lainnya , aspek unik dari tantangan ini membuatnya sangat berbeda.
Beth terletak di sebuah oasis di tengah padang pasir. Ada banyak air di danau, tetapi sayangnya hanya ada X ember, yang masing-masing memiliki kapasitas Y liter air.
Beth dapat membawa 2 ember di tangannya, tetapi untuk bertahan hidup, dia harus minum tepat 1 liter setelah setiap kilometer dia bepergian. Dia juga dapat meninggalkan beberapa ember setengah jalan (air tidak menguap).
Tantangan
Cari tahu rumusnya dan tulis solusi terpendek yang akan bekerja untuk nilai integer positif X dan Y dan hitung jarak maksimum yang dapat ditempuh Beth dari oasis. Air bergerak di antara ember diizinkan.
Contoh
X = 3, Y = 5
- Beth meninggalkan 1 ember penuh 3 KM jauhnya dari oasis, kembali (minum terakhir dari oasis)
- Beth membawa ember penuh pada titik 3KM, memiliki 12L di sana sekarang.
- Beth dapat maju ke titik 6km dan meninggalkan ember dengan 4L air di dalamnya.
- Kembali ke poin 3 KM. Dia sekarang memiliki tepat 2L untuk kembali ke oasis.
- Isi ember dan bepergian ke titik 6 KM. Dia sekarang memiliki 8L air.
- Lanjutkan sampai titik 15km.
Jawabannya adalah: 15
Input output
Anda dapat mendefinisikan X / Y secara langsung dalam kode atau membaca dari input. Hasil dapat ditempatkan dalam variabel atau output, mana yang terpendek.
sumber
Jawaban:
JavaScript (ES6), 25 byte
Semua ini menghitung nilai yang sama; Sepertinya saya tidak bisa menghasilkan formulasi yang lebih pendek.
Ketika
x
kurang dari3
, Anda mengambil air sebanyak yang Anda bisa dan berjalan sejauh yang Anda bisa, yang sederhanax*y+1
.Ketika
x
setidaknya 3, Anda harus mulai membuat cache.Dari oasis, Anda dapat meninggalkan ember penuh di kejauhan
y/2
dan kembali ke oasis. Anda perlu 2 ember untuk melakukan ini, tetapi ini tidak berguna jika Anda hanya memiliki 2 ember karena Anda ingin dapat mengisi 2 ember ketika Anda kembali ke oasis.Dari oasis, dengan ember di kejauhan
y/2
, Anda dapat meninggalkan ember penuh di kejauhany
dan kembali ke oasis. Anda perlu 3 ember untuk melakukan ini.Dari oasis, dengan ember penuh di keduanya
y
dany/2
, Anda dapat meninggalkan ember penuh di kejauhan3y/2
dan kembali ke oasis. Anda perlu 4 ember untuk melakukan ini. Anda kemudian harus meninggalkan ember penuh pada jaraky/2
dan kembali ke oasis.Akhirnya Anda bisa berakhir dengan ember penuh di
(x-1)y/2
. (Anda tidak dapat meninggalkan ember penuhxy/2
karena Anda tidak akan dapat kembali ke oasis, karena perjalanan pulang-pergixy
, kapasitas total ember.)Dengan menggunakan sisa ember, Anda dapat meninggalkan ember penuh di
(x-3)y/2
...y
atauy/2
. Pada titik ini Anda cukup berjalan sejauh yang Anda bisa, mengambil ember penuh Anda saat Anda pergi. Ketika Anda mencapai(x-1)y/2
Anda masih memiliki dua ember penuh yang tersisa, memungkinkan Anda untuk mencapai(x+3)y/2
.Ekstra
1
berasal dari kekhasan dalam aturan yang memungkinkan Anda untuk berjalan mil terakhir Anda tanpa air. Meskipun contoh menunjukkan bahwa Anda dapat meninggalkan ember sedikit lebih jauh dari yang dijelaskan di atas, ini sebenarnya tidak membantu Anda berjalan lebih jauh, karena Anda harus meninggalkan lebih sedikit air atau minum air dari ember saat Anda meraihnya sebelum Anda dapat memindahkan di.sumber