Ostatnio w Puzzling.SE napotkałem problem związany z określeniem, które dwie butelki z większej liczby są zatrute, gdy trucizna aktywuje się tylko wtedy, gdy oba składniki są pijane. Skończyło się to dość ciężką próbą, a większość ludzi zdołała sprowadzić go do 18 lub 19 więźniów przy użyciu zupełnie innych algorytmów.

Oryginalna deklaracja problemu jest następująca:

Jesteś władcą średniowiecznego królestwa, który uwielbia organizować przyjęcia. Dworzanin, który ostatni raz próbował otruć jedną z twoich butelek wina, był wściekły, gdy dowiedział się, że udało ci się zidentyfikować, którą butelkę zatruł na 1000 z zaledwie dziesięcioma więźniami.

Tym razem jest trochę bardziej sprytny. Opracował złożoną truciznę P : podwójny płyn, który jest śmiertelny tylko wtedy, gdy zmieszają się dwa indywidualnie nieszkodliwe składniki; jest to podobne do działania żywicy epoksydowej. Wysłał ci kolejną skrzynię 1000 butelek wina. Jedna butelka ma składnik, C_aa druga ma składnik C_b. ( P = C_a + C_b)

Każdy, kto pije oba składniki, umrze po północy w noc, w której wypił ostatni składnik, niezależnie od tego, kiedy w ciągu dnia wchłonął płyn. Każdy składnik trucizny pozostaje w ciele, dopóki drugi składnik nie zostanie aktywowany, więc jeśli wypijesz jeden składnik jednego dnia, a drugi następnego, umrzesz o północy pod koniec drugiego dnia.

Masz dwa dni do następnej imprezy. Jaka jest minimalna liczba więźniów, których należy użyć do testowania, aby zidentyfikować, które dwie butelki są skażone, i jakiego algorytmu należy przestrzegać przy tej liczbie więźniów?

---

Premia
Dodatkowo, przypuśćmy, że dysponowałeś stałym limitem 20 więźniów, jaka jest maksymalna liczba butelek, które możesz teoretycznie przetestować i dojść do dokładnego wniosku, na które butelki miało to wpływ?

Twoim zadaniem jest zbudowanie programu do rozwiązania problemu bonusowego. Biorąc pod uwagę nwięźniów, twój program opracuje harmonogram testów, który będzie w stanie wykryć dwie zatrute butelki wśród mbutelek, gdzie msą one tak duże, jak to możliwe.

Twój program początkowo przyjmie jako dane wejściowe liczbę N, liczbę więźniów. Następnie wyświetli:

• M, liczba butelek, które spróbujesz przetestować. Te butelki będą oznaczone od 1do M.

• N linie zawierające etykiety butelek, które wypije każdy więzień.

Twój program pobierze następnie dane wejściowe, którzy więźniowie zmarli pierwszego dnia, z więźniem w pierwszej linii 1, w kolejnej linii 2itd. Następnie wyświetli:

• Nwięcej linii, zawierających etykiety butelek, które każdy więzień wypije. Martwi więźniowie będą mieli puste linie.

Twój program następnie weźmie pod uwagę, którzy więźniowie zmarli drugiego dnia, i wyśle ​​dwie liczby, Ai Breprezentując, które dwie butelki twój program uważa za truciznę.

Przykładem wejście dla dwóch więźniów i cztery butelki może iść jako takie, czy butelek 1i 3są zatrute:

> 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.

Harmonogram testów Twojego programu musi z powodzeniem określać każdą możliwą parę zatrutych butelek, aby mogła być ważna.

Twój program będzie oceniany według następujących kryteriów, w kolejności:

• Maksymalna liczba butelek, jaką może rozpoznać dla skrzynki N = 20.

• Liczba butelek w skrzynce N = 21, a następnie kolejne skrzynie.

• Długość kodu. (Wygrywa krótszy kod).

Python 2.7.9 - 21 butelek

Zakładając, że spekulacje ESultanika są słuszne na temat wkładu, gdy wielu więźniów umiera

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])

Algorytm: każdy więzień pije z każdej butelki oprócz swojej liczby (pierwszy więzień nie pije pierwszej butelki). Jeśli nie umrą, ich butelka z liczbami jest zatruta. Jeśli przeżyje tylko jeden więzień, dodatkowa butelka jest zatruta.

Perl 5 , 66 butelek

(72 butelki dla 21 więźniów)

Więźniowie są optymalnie podzieleni na 2 grupy. Butelki są pogrupowane w zestawy.

Każdy więzień z grupy 1 będzie pił ze wszystkich zestawów oprócz jednego. Będzie 1 lub 2 ocalałych. 1 lub 2 zestawy, które nie zostały wypite, będą kontynuowane do drugiego dnia.

W drugim dniu pozostali więźniowie (w tym ci, którzy przeżyli) piją ze wszystkich pozostałych butelek oprócz jednej.
Kiedy 2 więźniów przeżyje, butelki, których nie wypili, są zatrute.
Jeśli pozostanie tylko 1 więzień, to butelka, którą wszyscy wypili, jest również podejrzana.

Kod zawiera dodatkową funkcjonalność ułatwiającą testowanie. Po dodaniu zatłoczonych butelek jako dodatkowych parametrów, nie poprosi on o informację o tym, kto zmarł.

($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"

Test

$ 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

Test bez ręcznego wprowadzania danych

$ 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

Zgodnie z tradycją opublikuję referencyjną odpowiedź na ostatnie miejsce.

Python - 7 butelek

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]

Niech każdy więzień wypije jedną możliwą parę butelek, z wyjątkiem pary dwóch ostatnich. Jeśli któryś z więźniów umrze, para, którą ten więzień pił, była zatruta. W przeciwnym razie zatrute zostały dwie ostatnie butelki.

Przydziały dla co najmniej n(n-1)/2 - 1więźniów można zrobić do nbutelek. Ponieważ n = 7ten dolny limit wynosi 20.

Potrzebujemy tylko jednego dnia, aby to rozwiązanie zadziałało. Dwudniowe rozwiązanie o podobnym zakresie może N = 20kosztować nawet 20 butelek , ale jest to zbyt wiele pracy, by uzyskać banalną odpowiedź.