I’ve written the following solution to the problem PHYSICS (PHYSICS Problem - CodeChef), 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[0]
used = h[1]
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.