Evil king and poissoned bottle
An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately they don’t know which one. To make the matter worse the poison the spy used was very deadly. Just one drop diluted even to a billion will still kill someone. Even so, the poison works slowly. It takes a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O(logn) of his taste testers.
Algorithm
Deci_to_bin(deci_no) // here deci_no is the decimal number which is converted to binary number bin_no using this algorithm 1. Set bin_no:=0 and n:=1; 2. Repeat steps 3 to 6 while(dec_no!=0) 3. Set rem:=dec_no%2; 4. Set bin_no:=bin_no + rem*n; 5. Set n:=n*10; 6. Set dec_no:=dec_no/2 7. [end of step 2] 8. Return bin_no; 9. [end] no_of_bin_digit(dec_no)//this algorithm counts number of binary digits 1. [Initialize count] count:=0; 2. Repeat steps 3 and 4 while dec_no!=0 3. [Increment count]count++; 4. Set dec_no:=dec_no/2; 5. [end of step 2] 6. Return count; 7. [End] Poisoned_bottle()//taster is an array of tasters who tastes the wine bottle. This algorithm computes the taster that would die on tasting the given wine bottle. 1. Set bin_bot:=0; 2. [Input the number of wine bottles] input bottle; 3. n := Call no_of_bin_digit(bottle); 4. [Input the bottle number that could be poisoned]input num; 5. Call deci_to_bin(num); 6. [Initialize taster] taster[i]=0 for i=1 to n; 7. Set index:=1; 8. Repeat steps 9 to 13 while bin_bot>0 9. Set rem := bin_bot%10; 10. If rem==1 then a. Set taster[index]:=1; 11. bin_bot := bin_bot/10; 12. [increase index] index++; 13. [end of step 8] 14. Repeat steps 15 and 16 for i=1 to n 15. If(taster [i]==1 && num>0) then: a. Return i; 16. Else print “No taster diedâ€; 17. [end of step 14] 18. [end]
Algorithm Description
Java Code
import java.io.*;
class evil_k{
int l,i;
int c=1;
void cr_t(int k)
{
l=(int)(Math.log(k)/Math.log(2));
System.out.print("\t |") ;
for(i=0;i<l;i++)
{
System.out.print(c+++"\t");
}
System.out.println("\t");
}
void bin(int m,int n)
{
int count=0;
l=(int)(Math.log(n)/Math.log(2));
int p[]=new int[l];
while(m!=0)
{
p[count]=m%2;
m=m/2;
count++;
}
i=l-1;
while(i>=0)
{
System.out.print(p[i]+"\t");
i--;
}
}
}
class evil_king{
public static void main(String args[]){
try{
evil_k ob=new evil_k();
int i;
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.print("enter the no. of wine bottles in powers of 2\n");
int k=Integer.parseInt(cin.readLine());
System.out.println("a testing sample consists of wine from the bottle having 1 in the corresponding column");
System.out.println("___________________________________________________");
System.out.println("bottle no. | tester no. ");
System.out.println("---------------------------------------------------");
ob.cr_t(k);
System.out.println("---------------------------------------------------");
for(i=0;i<k;i++)
{
if(i<9)
System.out.print(" "+(i+1)+" |");
else
System.out.print(" "+(i+1)+" |");
ob.bin(i,k );
System.out.println(" ");
}System.out.println("the poisoned bottle is the bottle whose row contains the 1's for the");
System.out.println(" corresponding testers who died");
}catch(Exception e){}
}
}
