Baru-baru ini di Puzzling.SE, ada masalah yang saya tulis tentang menentukan dua botol dari jumlah yang lebih besar yang diracuni ketika racun hanya aktif jika kedua komponen diminum. Itu akhirnya menjadi cobaan berat, dengan sebagian besar orang berhasil menurunkannya menjadi 18 atau 19 tahanan menggunakan algoritma yang sama sekali berbeda.

Pernyataan masalah asli adalah sebagai berikut:

Anda adalah penguasa kerajaan abad pertengahan yang suka mengadakan pesta. Petugas pengadilan yang mencoba meracuni salah satu botol anggur Anda terakhir kali sangat marah mengetahui bahwa Anda berhasil mengidentifikasi botol mana yang telah diracuni dari 1.000 botol dengan hanya sepuluh tahanan.

Kali ini dia sedikit rajin. Dia mengembangkan racun komposit P : cairan biner yang hanya mematikan ketika dua komponen yang tidak berbahaya bercampur secara individu; ini mirip dengan cara kerja epoksi. Dia mengirimi Anda peti berisi 1.000 botol anggur lagi. Satu botol memiliki komponen C_adan yang lain memiliki komponen C_b. ( P = C_a + C_b)

Siapa pun yang minum kedua komponen akan mati pada tengah malam pada malam mereka minum komponen terakhir, terlepas dari kapan di hari mereka menyerap cairan. Setiap komponen racun tetap berada di dalam tubuh sampai komponen kedua aktif, jadi jika Anda minum satu komponen satu hari dan komponen lainnya di hari berikutnya, Anda akan mati pada tengah malam di akhir hari kedua.

Anda memiliki dua hari sebelum pesta berikutnya. Berapa jumlah minimum tahanan yang perlu Anda gunakan untuk pengujian untuk mengidentifikasi dua botol yang tercemar, dan algoritma apa yang perlu Anda ikuti dengan jumlah tahanan itu?

---

Bonus
Selain itu, anggaplah Anda memiliki batas tetap 20 tahanan yang Anda miliki, berapa jumlah botol maksimum yang dapat Anda uji secara teoritis dan sampai pada kesimpulan yang akurat tentang botol mana yang terpengaruh?

Tugas Anda adalah membangun program untuk memecahkan masalah bonus. Diberikan ntahanan, program Anda akan menyusun jadwal pengujian yang akan dapat mendeteksi dua botol beracun di antara mbotol, di mana msebesar mungkin.

Program Anda awalnya akan mengambil sebagai input nomor N, jumlah tahanan. Maka akan ditampilkan:

• M, jumlah botol yang akan Anda coba untuk menguji. Botol-botol ini akan diberi label dari 1ke M.

• N baris, berisi label botol masing-masing tahanan akan minum.

Program Anda kemudian akan mengambil input tahanan mana yang mati di hari pertama, dengan tahanan di baris pertama 1, baris berikutnya 2, dll. Lalu, itu akan menampilkan:

• Nlebih banyak garis, berisi label botol yang akan diminum setiap tahanan. Tahanan yang mati akan memiliki garis kosong.

Program Anda kemudian akan mengambil input tahanan mana yang mati pada hari kedua, dan menghasilkan dua angka, Adan B, mewakili dua botol mana yang menurut program Anda mengandung racun.

Contoh input untuk dua tahanan dan empat botol mungkin seperti itu, jika botol 1dan 3diracuni:

> 2      // INPUT: 2 prisoners
4        // OUTPUT: 4 bottles
1 2 3    // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4      // OUTPUT: prisoner 2 will drink 1, 4
> 1      // INPUT: only the first prisoner died
         // OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3        // OUTPUT: prisoner 2 drinks bottle 3
> 2      // INPUT: prisoner 2 died
1 3      // OUTPUT: therefore, the poisoned bottles are 1 and 3.

The above algorithm may not actually work in all
cases; it's just an example of input and output.

Jadwal pengujian program Anda harus berhasil menentukan setiap kemungkinan pasangan botol beracun agar dapat menjadi pengiriman yang valid.

Program Anda akan dinilai berdasarkan kriteria berikut, dalam urutan:

• Jumlah botol maksimum yang dapat dilihat untuk kasing N = 20.

• Jumlah botol untuk kasing N = 21, dan kasing lebih tinggi setelahnya.

• Panjang kode. (Kode pendek menang.)

Python 2.7.9 - 21 botol

Dengan anggapan bahwa spekulasi ESultanik benar tentang apa inputnya ketika banyak tahanan mati

r=raw_input;s=str;j=s.join;p=int(r());z=range;q=z(p);x=z(p+1)
print s(p+1)+"\n"+j("\n",(j(" ",(s(a) for a in x if a!=b)) for b in q))
v=r().split();d=[s(a) for a in q if s(a) not in v];d+=[p]if len(d)==1 else [];
print "\n"*p,;r();print j(" ",[s(a) for a in d])

Algoritma: setiap tahanan minum dari setiap botol kecuali nomor mereka (tahanan pertama tidak minum botol pertama). Jika mereka tidak mati, botol nomor mereka diracuni. Jika hanya satu tahanan yang selamat, botol ekstra itu diracuni.

Perl 5 , 66 botol

(72 botol untuk 21 tahanan)

Para tahanan dibagi secara optimal menjadi 2 kelompok. Botol dikelompokkan dalam set.

Setiap tahanan dari grup 1 akan minum dari semua set kecuali satu. Akan ada 1 atau 2 yang selamat. Set 1 atau 2 yang tidak diminum akan berlanjut hingga hari ke 2.

Pada hari ke-2 tahanan yang tersisa (termasuk yang selamat) minum dari semua botol yang tersisa kecuali satu.
Ketika 2 tahanan bertahan hidup maka botol yang tidak mereka minum diracun.
Jika hanya 1 tahanan yang tersisa maka botol yang mereka minum juga mencurigakan.

Kode ini mencakup fungsionalitas tambahan untuk memfasilitasi pengujian. Ketika botol poisened ditambahkan sebagai parameter tambahan, maka itu tidak akan meminta masukan tentang siapa yang mati.

($p,$f,$l)=@ARGV;
$p=9if!$p;
$m=$p-(2*int($p/4))+1;
$n=$p-$m+2;
$b=$m*(($n+1)/2);
@M=(1..$m);
print"Prisoners: $p\nBottles: $b\n";
# building the sets of items
for$x(@M){
    $j=$k+1;$k+=($n+1)/2;
    $s=join",",($j..$k);
    $A[$x]=$s
}
# assigning the sets to the actors
for$x(@M){
    @T=();
    for$j(@M){if($x!=$j){push@T,split/,/,$A[$j]}}
    print"Prisoner $x drinks @T\n";
    $B[$x]=join",",@T
}
if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=split/ /;
    %h=map{($_,1)}@D;
    @S=grep{!$h{$_}}(@M)
} 
else{
    # calculate who dies based on the parameters
    for$x(@M){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@S,$x}
    }
}
for(@D){print"Prisoner $_ dies\n"}

# calculate the remaining items
for(@S){push@R,split/,/,$A[$_]}@R=sort{$a<=>$b}grep{!$g{$_}++}@R;

# different set of actors if there were 1 or 2 sets remaining
if(@S>1){@S=($S[0],$m+1..$p,$S[1],0)}else{@S=($m+1..$p)};

$i=0;@B=@D=();
# assign an item to each actor
for$x(@S){
    @T=();
    for($j=0;$j<@R;$j++){
        if($i!=$j){push@T,$R[$j]}
    }$i++;
    print"Prisoner $x drinks @T\n"if$x>0;
    $B[$x]=join",",@T
}

if(!$f||!$l){
    # manual input
    print"Who dies: ";
    $_=<STDIN>;chomp;
    @D=sort split/ /;
    if(@D<@S-1){push@D,0} # because the set that noone drinks isn't manually put in
    %h=map{($_,1)}@D;
    @L=grep{!$h{$_}}(@S);
}
else{
    # calculate who dies based on the parameters
    @D=();
    for$x(@S){
        $d=0;
        map{if($_==$f||$_==$l){$d++}}split/,/,$B[$x];
        if($d>1){push@D,$x}else{push@L,$x}
    }
}

for(@D){print"Prisoner $_ dies\n"if$_>0}

# calculate the remaining items
for(@L){push@F,split/,/,$B[$_]}
map{$c{$_}++}@F;
for(keys%c){push(@Z,$_)if$c{$_}==1}
@R=sort{$a<=>$b}@Z;

print"Suspected bottles: @R"

Uji

$ perl poisened_bottles.pl 20
Prisoners: 20
Bottles: 66
Prisoner 1 drinks 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 2 drinks 1 2 3 4 5 6 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 3 drinks 1 2 3 4 5 6 7 8 9 10 11 12 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 4 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 5 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 7 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 8 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 9 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 55 56 57 58 59 60 61 62 63 64 65 66
Prisoner 10 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 61 62 63 64 65 66
Prisoner 11 drinks 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
Who dies: 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 3 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 7 dies
Prisoner 8 dies
Prisoner 9 dies
Prisoner 10 dies
Prisoner 1 drinks 2 3 4 5 6 61 62 63 64 65 66
Prisoner 12 drinks 1 3 4 5 6 61 62 63 64 65 66
Prisoner 13 drinks 1 2 4 5 6 61 62 63 64 65 66
Prisoner 14 drinks 1 2 3 5 6 61 62 63 64 65 66
Prisoner 15 drinks 1 2 3 4 6 61 62 63 64 65 66
Prisoner 16 drinks 1 2 3 4 5 61 62 63 64 65 66
Prisoner 17 drinks 1 2 3 4 5 6 62 63 64 65 66
Prisoner 18 drinks 1 2 3 4 5 6 61 63 64 65 66
Prisoner 19 drinks 1 2 3 4 5 6 61 62 64 65 66
Prisoner 20 drinks 1 2 3 4 5 6 61 62 63 65 66
Prisoner 11 drinks 1 2 3 4 5 6 61 62 63 64 66
Who dies: 1 12 14 15 16 17 18 20 11
Prisoner 1 dies
Prisoner 11 dies
Prisoner 12 dies
Prisoner 14 dies
Prisoner 15 dies
Prisoner 16 dies
Prisoner 17 dies
Prisoner 18 dies
Prisoner 20 dies
Suspected bottles: 3 63

Tes tanpa input manual

$ perl poisened_bottles.pl 7 2 5
Prisoners: 7
Bottles: 12
Prisoner 1 drinks 3 4 5 6 7 8 9 10 11 12
Prisoner 2 drinks 1 2 5 6 7 8 9 10 11 12
Prisoner 3 drinks 1 2 3 4 7 8 9 10 11 12
Prisoner 4 drinks 1 2 3 4 5 6 9 10 11 12
Prisoner 5 drinks 1 2 3 4 5 6 7 8 11 12
Prisoner 6 drinks 1 2 3 4 5 6 7 8 9 10
Prisoner 2 dies
Prisoner 4 dies
Prisoner 5 dies
Prisoner 6 dies
Prisoner 1 drinks 2 5 6
Prisoner 7 drinks 1 5 6
Prisoner 3 drinks 1 2 6
Prisoner 1 dies
Suspected bottles: 2 5

Seperti tradisi, saya akan memposting jawaban referensi tempat terakhir.

Python - 7 botol

prisoners = int(raw_input())

bottles = 0
while (bottles * (bottles + 1) / 2 - 1) <= prisoners:
    bottles += 1

print bottles

pairs = []
for i in range(bottles):
    for j in range(i + 1, bottles):
        pairs += [str(i + 1) + " " + str(j + 1)]

for i in range(prisoners):
    if i < len(pairs):
        print pairs[i]
    else:
        print

dead_prisoner = raw_input()

for i in range(prisoners):
    print
raw_input() # discard the second day entirely

if dead_prisoner == "":
    print pairs[-1]
else:
    print pairs[int(dead_prisoner) - 1]

Buat setiap tahanan minum satu botol yang mungkin kecuali untuk dua botol terakhir. Jika ada tahanan yang mati, pasangan yang diminum oleh tahanan itu adalah yang beracun. Kalau tidak, itu dua botol terakhir yang diracuni.

Untuk penjatahan setidaknya n(n-1)/2 - 1tahanan, Anda dapat melakukan hingga nbotol. Sebab n = 7, batas bawah ini adalah 20.

Kami hanya membutuhkan satu hari agar solusi ini berfungsi. Solusi dua hari dengan ruang lingkup yang sama mungkin mendapatkan hingga 20 botol N = 20, tetapi itu terlalu banyak untuk jawaban sepele.