Pertimbangkan semua 2^n
panjang string biner yang berbeda n
dan asumsikan n > 2
. Anda diizinkan untuk menghapus b < n/2
bit tepat dari masing-masing string biner, meninggalkan string yang n-b
tersisa. Jumlah string berbeda yang tersisa tergantung pada bit mana yang Anda hapus. Dengan asumsi tujuan Anda adalah untuk meninggalkan string yang tersisa sesedikit mungkin, tantangan ini adalah menulis kode untuk menghitung berapa sedikit yang dapat Anda tinggalkan sebagai fungsi n
.
Contoh, n=3
dan b = 1
. Anda hanya dapat meninggalkan dua string 11
dan 00
.
Untuk n=9
dan b = 1,2,3,4
kita miliki70,18,6,2
Untuk n=8
dan b = 1,2,3
kita miliki40,10,4
Untuk n=7
dan b = 1,2,3
kita miliki20,6,2
Untuk n=6
dan b = 1,2
kita miliki12,4
Untuk n=5
dan b = 1,2
kita miliki6,2
Pertanyaan ini awalnya diajukan oleh saya pada tahun 2014 dalam bentuk berbeda di MO .
Masukan dan keluaran
Kode Anda harus mengambil bilangan bulat n
dan mengeluarkan bilangan bulat tunggal untuk setiap nilai b
mulai b = 0
dan meningkat.
Skor
Skor Anda adalah yang terbesar n
yang menyelesaikan kode Anda untuk semua b < n/2
dalam waktu kurang dari satu menit pada PC berbasis Linux saya. Jika terjadi break tie, b
kode Anda yang terbesar didapat untuk n
kemenangan terbesar bersama . Dalam kasus tie break pada kriteria itu juga, kode tercepat untuk nilai-nilai terbesar n
dan b
memutuskan. Jika waktunya dalam satu atau dua detik satu sama lain, jawaban yang diposting pertama menang.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa perpustakaan apa pun yang Anda suka. Karena saya harus menjalankan kode Anda, itu akan membantu jika itu gratis (seperti bir) dan bekerja di Linux.
sumber
b > 0
sebagai persyaratan input tambahan? Atau akann=3
danb=0
hanya menampilkan2^n
sebagai hasilnya?2^n
memang menghasilkan .n
dan tunggalb
, tetapi skornya adalah yang terbesarn
yang menyelesaikan semua kodeb < n/2
dalam waktu kurang dari satu menit. Bukankah lebih baik memiliki satu inputn
dalam kasus itu, dan mengeluarkan semua hasil0 <= b < n/2
? Atau haruskah kita menyediakan dua program / fungsi: satu mengambil dua inputn
danb
, dan satu hanya mengambil inputn
dan mengeluarkan semua hasil dalam rentang0 <= b < n/2
?Jawaban:
Python 2.7 / Gurobi n = 9
Solusi ini sangat mudah digunakan solver Gurobi's ILP untuk boolean Mixed-Integer Problems (MIP).
Satu-satunya trik adalah mengambil simetri dalam komplemen 1 untuk membagi dua ukuran masalah.
Menggunakan lisensi "bebas" terbatas Gurobi LLC, kami dibatasi hingga 2000 kendala, tetapi menyelesaikan 10 del 1 masih di luar batas waktu 60 detik di laptop saya.
UPDATE + CORR: 10,2 memiliki ukuran solusi optimal 31 (lihat misalnya) Gurobi tidak menunjukkan solusi simetris ukuran 30 ada (mengembalikan masalah tidak layak) .. [usaha saya untuk menunjukkan kelayakan asimetris pada 30 tetap tidak meyakinkan setelah runtuh 9,5 jam] misalnya bit pola bilangan bulat
0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255
atau0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255
sumber
C ++, n = 6
Brute force dengan beberapa optimasi kecil.
Jalankan secara lokal:
sumber