I’ve written the following solution to the problem PHYSICS (http://www.codechef.com/problems/PHYSICS), it passes the simple test case provided but on submitting its results in WA(wrong answer) for all test cases.
import numbers T = input() for t in xrange(T): N, F = [int(i) for i in raw_input().split()] heights = [(long(i), False) for i in raw_input().split()] heights.sort() heights.reverse() ways = 0 for i, h in enumerate(heights): height = h used = h if used: continue j = 0 while True: force = F ** j if force > height: break bounce = height / force if isinstance(bounce, numbers.Integral): try: if len(heights) > i: index = heights.index((bounce, False), i + 1) if index != i: heights[index] = (bounce, True) ways += 1 break except ValueError: pass finally: j += 1 print ways
This is what I’m doing in my solution :
- for all the children in classroom
heights list stores tuple(height,
used) where height is the height of a
child and boolean used indicates if
child has been already used in
forming a pair or not.
- the while loop
checks if there’s child whose height
is equal to for all possible bounces
Help me spot the cases where this
solution can fail, and the fix.