#include <iostream> #include <vector> #include <math.h> using namespace std; /* * DEBUG ONLY: If compiled -DDEBUG, the parameters computed for each stronghold * will be printed out to stderr. */ /* SANITY CHECK: assertion macro for verifying input data */ #define ASSERT(e) { if(!(e)) { cerr << #e << endl; throw; } } /* SANITY CHECK: maximum input values as defined in problem statement */ #define MAX_N 100 #define MAX_E 20 #define MAX_D 10000 #define MAX_J 10000 #define MAX_S 50 #define MAX_I 30000 /* Data structure representing a single stronghold from the input */ typedef struct { int D; /* Distance of stronghold from invader's starting position */ int J; /* Strength of defenders */ int S; /* Strength of the stronghold */ } hold_t; /* Less than operator for sorting a vector<hold_t> by stronghold distance */ inline bool operator<(hold_t const &a, hold_t const &b) { return a.D < b.D; } /* Main body of program */ void process(void) { int data_idx, data_num; /* Read how many datasets to process */ cin >> data_num; ASSERT(data_num >= 1 && data_num <= MAX_N); /* Simulate each dataset separately */ for(int data_idx = 0; data_idx < data_num; data_idx++) { vector<hold_t> holds; int hold_idx, hold_num; int start = 0; /* Current position of invading force */ int I; /* Current strength of invading force */ /* Read in total number of strongholds */ cin >> hold_num; ASSERT(hold_num >= 1 && hold_num <= MAX_E); /* Read in each stronghold definition */ for(hold_idx = 0; hold_idx < hold_num; hold_idx++) { hold_t hold; cin >> hold.D >> hold.J >> hold.S; ASSERT(hold.D >= 1 && hold.D <= MAX_D); ASSERT(hold.J >= 1 && hold.J <= MAX_J); ASSERT(hold.S >= 1 && hold.S <= MAX_S); holds.push_back(hold); } /* Sort the list of strongholds by their distance */ sort(holds.begin(), holds.end()); /* Read in initial strengh of the invading force */ cin >> I; ASSERT(I >= 1 && I <= MAX_I); /* Run through each of the strongholds in order */ for(hold_idx = 0; hold_idx < hold_num; hold_idx++) { hold_t &hold = holds[hold_idx]; /* Current hold being processed */ int F = I * (hold.D - start); /* Invading force */ int B = hold.J * hold.S * hold.S; /* Defending force */ #ifdef DEBUG /* DEBUG ONLY: Print out current stronghold being processed */ cerr << hold.D << " " << hold.J << " " << hold.S << endl; /* DEBUG ONLY: Print out computed parameters for this stronghold */ cerr << "I=" << I << " D=" << (hold.D - start); cerr << " F=" << F << " B=" << B << endl; #endif /* Check if the invading force has been stopped */ if(F <= B) { #ifdef DEBUG cerr << "RETREAT!" << endl; #endif cout << "RETREAT!" << endl; break; } /* Adjust invador's current strength and position */ I = (int) ceil( I * (1.0 - ((float)B) / F) ); start = hold.D; } /* Check if the invaders made it through all strongholds */ if(hold_idx == hold_num) { #ifdef DEBUG cerr << "ROUT!" << endl; #endif cout << "ROUT!" << endl; } } } /* Run program and print out any exceptions that occur */ int main(void) { /* Throw exceptions on failed data extraction in >> operator */ cin.exceptions(ios::failbit); /* Run main body of code */ try { process(); } /* Catch unexpected EOF or bad input data */ catch(ios::failure const &e) { cerr << "Unexpected EOF or data type mismatch on input" << endl; } return 0; }