A solution by using 4-based number


  • 0
    X

    Water the pig every 15 minutes.
    Then a single pig can have exactly 4 status:
    Alive/die at 15
    Alive/die at 30
    Alive/die at 45
    Alive/die at 60

    x pigs has 4^x different status. We want 4^x>=1000, then x>=5(which makes an 1024).
    It equals to: we are now using a 4-based numeric system, then how many digits are there should we use to represent a number greater than a decimal 1000?

    (The answer is 5, too, since these two questions equals to the other.)

    If we have x pigs, poison in m minutes, total time span is p minutes, n buckets, the answer is:
    Different status: d=Ceil(p/m)
    x=Ceil(log(d,n))

    Then we have(left column is 10 based, right column is 4 based):
    00000-00000
    00001-00001
    00002-00002
    00003-00003
    00004-00010
    00005-00011
    00006-00012
    ...
    00999-33213
    0-999 are the bucket IDs.

    Water the pig in this way:
    For the bucket with ID n(based 10), find out the respective base-4 number, e.g.:
    00999-33213
    Water the first pig at 45(first digit in base 4 is 3, 3*15=45)
    Water the second pig at 45
    Water the third pig at 30
    Water the forth pig at 15
    Water the fifth pig at 45

    If the bucket 999 is poison, then
    First pig dies at 60
    Second 60
    Third 45
    Forth 30
    Fifth 60

    Since no other bucket ID is encoded to 33213, we can make sure that if/only if bucket 999 is poison, the five pigs will have the status above.

    On the other hand if we observe that:
    First pig dies at 60, second 60, third 45, forth 30, fifth 60, we know that the corresponding 4-based number is: 3/3/2/1/3, and the 10-based ID is 999.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.