''' EVIL-KING PROBLEM
To find the poisoned bottle from n bottles with order of log(n) taseters'''
import sys
from time import clock

def no_of_bin_digit(k):
    count=0
    while(k!=0):
        count=count+1
        k=k/2
    return count

def main():
    start = clock()
    taster=[]
    fin=open("in11_8.txt","r")
    fout=open("out_28_11_8.txt","w")
    t=[]
    for x in fin.readlines():
        for y in x.split(','):
            y=y.strip()
            t.append(int(y))
    bottles= t[0]
    t=t[1:]
    
    n=no_of_bin_digit(bottles)
    
    
    for i in range(0,n):
        taster.append(0)
        
    for i in range(0,len(t)):
        if(t[i]<=n):
            taster[t[i]-1]=1
        else:
            fout.write ("Wrong Choice")

    # to find decimal equivalent
    taster=taster[::-1]
    num=0                    
    base=1
    for i in range(0,len(taster),1):
        if (int(taster[i])==1):
            num=num + (int(taster[i])*base)
        base=base+base


    if(num<=bottles):
        #print("\nThe bottle number poisoned= ",num)
        fout.write(str(num))
    else:
        fout.write("\nYou entered wrong values for tasete testers")

    end = clock()
    m=0
    time= end - start
    fout.write("\n\n Total execuion time ="+ str(time)+ " seconds")
    m=m+sys.getsizeof(taster)+sys.getsizeof(t)+sys.getsizeof(x)+sys.getsizeof(bottles)+   sys.getsizeof(y)+sys.getsizeof(num)+sys.getsizeof(base)+sys.getsizeof(fin)+sys.getsizeof(fout)
    fout.write("\n Memory used= "+str(m)+" bytes")
    fin.close()
    fout.close()

main()