Guest User

Untitled

a guest
Feb 20th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. import random
  2.  
  3. def request(offset, query, new_query, chunk_len):
  4. [print(offset + pos + 1, end=' ') for pos in range(0, chunk_len) if (query ^ new_query) & (1 << pos)]
  5. print(flush=True)
  6. return int(input())
  7.  
  8. def find_chunk(n, offset, fitness, out_fitness):
  9. def remove_from_suitable_queries(suitable_queries, query, fitness):
  10. return [q for q in suitable_queries if (bin(2**n - 1 - (query ^ q)).count("1")) == fitness]
  11. query = (1 << n) - 1
  12. suitable_queries = remove_from_suitable_queries(list(range(0, 2**n)), query, fitness)
  13. new_fitness = fitness
  14. while len(suitable_queries) > 1:
  15. new_query = random.choice(suitable_queries)
  16. new_fitness = request(offset, query, new_query, n) - out_fitness
  17. suitable_queries = remove_from_suitable_queries(suitable_queries, new_query, new_fitness)
  18. query = new_query
  19.  
  20. if new_fitness != n:
  21. request(offset, query, suitable_queries[0], n)
  22.  
  23. n, fitness = tuple(int(x) for x in input().split())
  24. chunk_len = 8
  25. for i in range(0, int(n / chunk_len) + 1):
  26. if fitness == n:
  27. break
  28. step = min(chunk_len, n - i * chunk_len)
  29. offset = i * chunk_len
  30. new_fitness = request(offset, 0, (1 << step) - 1, step)
  31. chunk_fitness = int((step + new_fitness - fitness) / 2)
  32. find_chunk(step, offset, chunk_fitness, new_fitness - chunk_fitness)
  33. fitness = new_fitness - chunk_fitness + step
Add Comment
Please, Sign In to add comment