Mancala adalah nama keluarga permainan papan yang biasanya melibatkan serangkaian piala berisi manik-manik yang dimanipulasi oleh pemain. Tantangan ini akan menggunakan aturan khusus yang ditetapkan untuk varian solitaire permainan.
Papan terdiri dari "keranjang" di salah satu ujungnya, diikuti oleh jumlah cangkir yang tak terbatas, bernomor mulai dari 1. Beberapa cangkir akan memiliki sejumlah manik-manik di dalamnya. Jika n
cangkir th persis memiliki n
manik-manik di dalamnya, Anda dapat "menabur" manik-manik itu. Menabur berarti mengeluarkan semua n
manik - manik dari cangkir, lalu menyimpannya satu per satu di setiap cangkir ke arah keranjang. Manik terakhir akan masuk ke keranjang. Pemain menang ketika semua manik-manik di papan ada di keranjang.
Jelas, ada banyak papan yang tidak dapat dimenangkan, seperti jika ada tepat satu manik di piala kedua. Tidak ada permainan legal karena semua cangkir dengan 0 manik-manik tidak dapat ditaburkan, dan cangkir kedua tidak memiliki cukup manik-manik untuk ditabur. Ini jelas tidak menyenangkan, jadi tugas Anda adalah membuat papan yang dapat dimenangkan.
Tugas
Diberikan bilangan bulat positif yang mewakili sejumlah keluaran manik-manik, daftar bilangan bulat non-negatif mewakili jumlah manik-manik yang harus diletakkan di setiap cangkir untuk membuat papan yang dapat dimenangkan seperti dijelaskan di atas. Daftar ini tidak boleh mengandung nol yang tertinggal.
Untuk jumlah manik-manik tertentu, selalu ada persis satu konfigurasi papan yang dapat dimenangkan.
Demonstrasi
Ini adalah demonstrasi cara memainkan papan yang dapat dimenangkan dan input 4. Papan yang dapat dimenangkan adalah [0, 1, 3]
. Kami mulai dengan satu-satunya langkah yang tersedia, menabur manik-manik dari cangkir ketiga untuk mendapatkan [1, 2, 0]
. Sekarang kita benar-benar punya pilihan, tapi satu-satunya yang benar menabur cangkir pertama, mendapatkan: [0, 2, 0]
. Lalu kami menabur cangkir kedua menghasilkan [1, 0, 0]
dan akhirnya kami menabur cangkir pertama lagi untuk mendapatkan semua cangkir kosong.
Kasus uji:
1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]
Terima kasih banyak kepada PeterTaylor yang telah membuat program untuk menghasilkan kasus uji!
sumber
Jawaban:
CJam (21 byte)
Demo online
Penjelasan
Saya secara mandiri mendapatkan teknik "tidak dimainkan" yang disebutkan dalam makalah ini . Kami membuktikan dengan induksi bahwa ada tepat satu papan pemenang untuk jumlah manik-manik tertentu.
Kasus dasar: dengan 0 manik-manik, satu-satunya papan yang menang adalah yang kosong.
Langkah induktif: jika kita menabur dari cangkir
k
maka pada langkah selanjutnya cangkirk
akan kosong dan setiap cangkir lebih dekat keranjang akan berisi setidaknya satu manik. Oleh karena itu kita dapat menemukan papan kemenangan unik dengann
manik - manik dari papan kemenangan dengann-1
manik - manik dengan mencari cangkir kosong bernomor terendah, mengambil satu manik-manik dari keranjang dan satu dari setiap cangkir di bawah cangkir kosong, dan menempatkan semuanya di cangkir kosong.Pembedahan
sumber
Python,
4241 bytesumber
JavaScript (ES6),
6337 bytePort of @ orlp's Python answer. Penjelasan: Pertimbangkan jumlah total manik-manik di
i
gelas ke - t dan yang lebih tinggi. Setiap permainan dari salah satu cangkir ini akan menghilangkani
manik-manik dari total itu. (Misalnya, jikai
adalah 3, dan Anda bermain dari cangkir kelima, Anda mengurangi jumlah manik-manik di cangkir itu menjadi lima, tetapi Anda juga menambahkan satu ke cangkir keempat dan ketiga.) Oleh karena itu totalnya harus kelipatan darii
. Sekarangi-1
cangkir th tidak dapat berisii
atau lebih banyak manik-manik, sehingga agar dapat meninggalkan kelipatan darii
itu harus mengandung sisa modulo manik-maniki
.Penjelasan sebelumnya (dari tautan @ xnor): Pendekatan naif adalah teknik "bermain terbalik". Ini menggunakan pengamatan yang membuat permainan mengosongkan cangkir, jadi bermain terbalik mengumpulkan manik-manik dari setiap cangkir dan menempatkannya di cangkir kosong pertama, seperti (63 byte):
Sekarang, pertimbangkan
i
cangkir pertama . Jika salah satu dari mereka kosong, pemutaran terbalik akan menambah1
jumlah total manik-manik di cangkir itu, sedangkan dalam kasus tidak ada yang kosong, pemutaran terbalik akan mengurangii
total, namun ini setara dengan menambahkan1
modulo.i+1
. Setelahn
memutar ulang jumlah manik-manik dii
cangkir pertama karena itu akan sama dengann
moduloi+1
, atau dengan kata lain, jumlah manik-manik dii
cangkir th akan sama dengann
minus jumlah manik-manik di gelas sebelumnya, moduloi+1
. Sekarang untuki
cangkir yang dapat dimainkan jumlah manik-manik tidak dapat melebihii
, jadi sebenarnya itu akan sama dengan jumlah manik-manik modulo yang tersisai+1
. (Perhatikan bahwa saya menggunakand=i+1
karena menggunakan lebih sedikit byte.)sumber
+
bukan sesuatu di ES6?Ruby, 36 byte
Port jawaban @ orlp karena terlalu jenius bagi saya untuk memikirkan sesuatu yang lebih baik.
sumber