Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random
- def getmin(data, start, end, total_items):
- if total_items == 1:
- #for sure we have a fake coin
- return (0, start)
- elif total_items == 2:
- if data[start] > data[end]:
- return (1, end)
- elif data[start] < data[end]:
- return (1, start)
- else:
- partition = total_items/3
- a_weight = sum(data[start:start+partition])
- b_weight = sum(data[start+partition:start+2*partition])
- c_weight = sum(data[start+2*partition:end])
- if a_weight == b_weight:
- result = getmin(data, start+2*partition, end, end-(start+2*partition))
- return (1+result[0], result[1])
- else:
- if a_weight > b_weight:
- result = getmin(data, start+partition, start+2*partition, partition)
- return (1+result[0], result[1])
- else:
- result = getmin(data, start, start+partition, partition)
- return (1+result[0], result[1])
- n = int(raw_input())
- data = [1]*n
- data[random.randint(0, n-1)] = 0
- total_weighing, position = getmin(data, 0, len(data), len(data))
- print(total_weighing, position)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement