#!/usr/bin/env python # Rout # Phil Bordelon import os import sys DEBUG = os.getenv("DEBUG", False) def simulate (strongholds, invader_strength): # This is the main simulation section of the code. # Invaders start at distance 0, and they've yet to encounter any # strongholds. invader_pos = 0 stronghold_num = 0 # We use a while 1 loop because, uh, I change styles reguarly while # coding under pressure for projects that don't last. This is # ostensibly the "Pythonic" way; those of us trained on single-exit # loops may find it a little bothersome, but it works surprisingly # well. while 1: # Pull out the information from the stronghold. location, blocking_force = strongholds[stronghold_num] # Calculate the routing force, based on the distance from where the # invaders currently are to the location of the stronghold. distance = location - invader_pos routing_force = distance * invader_strength if DEBUG: print "I = %d | R = %d | B = %d" % (invader_strength, routing_force, blocking_force) # If they're not strong enough, we're done; they have to retreat. if routing_force <= blocking_force: return "RETREAT!" # It seems the routing force is greater; reduce the invader's # strength, using the formula from the problem ... except that # with Python it's not quite that easy. int(ceil(num)) generally # works ... except for when ceil(num) actually returns something # just a /wee/ bit above the number, thanks to floating point # craziness. # # I originally had an annoying hack in here to handle that (adding .999 # to the number and relying on the fact that int(n) rounds down towards # zero), which worked fine. However, a much more elegant solution # reveals itself if you actually take the equation for calculating the # new invader strength and simplify: # # Inew = ceil(Iold * (1 - B / F)) # Inew = ceil(Iold - Iold * B / F) # Inew = ceil(Iold - Iold * B / (Iold * D)) # Inew = ceil(Iold - B / D) # # That's right; the only actual factor that's relevant is B / D. # So we calculate that, and use Python's int(n) round-towards-zero to # substitute for having to use ceil(), as the results are identical. # Clever, no? reduction_factor = int(float(blocking_force) / distance) invader_strength -= reduction_factor # ... and move them to their new location at the stronghold. invader_pos = location # Increment the stronghold number ... stronghold_num += 1 # ... and if we're at the end of the strongholds, the rout succeeded. if stronghold_num == len(strongholds): return "ROUT!" if "__main__" == __name__: dataset_count = int(sys.stdin.readline()) for dataset_loop in range(dataset_count): # Read in the strongholds. strongholds = [] stronghold_count = int(sys.stdin.readline()) for stronghold_loop in range(stronghold_count): # Break out the elements of each stronghold. distance, def_strength, strong_strength = [int(x) for x in sys.stdin.readline().strip().split()] # There's no reason to keep around the separate values for # strongholds; the only relevant value is Blocking Force. blocking_force = def_strength * strong_strength * strong_strength # Store the distance and blocking force. strongholds.append((distance, blocking_force)) # Sort the strongholds by distance. Yay for Python tuples! strongholds.sort() # Read in the invader's strength. invader_strength = int(sys.stdin.readline()) # Run the rout simulation. print simulate(strongholds, invader_strength)