2014
01-05

# Rout 66

While the Romans may have had a fancy number system, the Visigoths (led by Alareiks, known now as Alaric I) managed to take Rome on August
24, 410. This was the first time that Rome had been taken by foreign troops in eight hundred years.

You will simulate a considerably less bloody (and less realistic) rout of soldiers by a potentially overwhelming force.

Consider a group of invaders of strength I, and an opposing force of strength J, with distance D between them and a defensive stronghold of strength
S. The Routing Force F of the invaders can be calculated as their strength times the distance:

F = ID

and the Blocking Force B of the defenders can be calculated as their strength times the square of their defenses:

B = JS2

If F is less than or equal to B, the invaders’ rout fails, and they are driven off. If F is greater than B, the rout is successful, all defenders of the
stronghold are driven off, and the invaders can continue. However, their strength is reduced by removing a fraction equal to the ratio of the
defenders’ Blocking Force to their Routing Force for that attack. The resulting number should be rounded up to the nearest integer, to ensure that a
successful rout leaves at least one soldier:

Inew = ?I(1 – B/F)?

If the invaders make it through a stronghold, its location is considered the starting point for calculations regarding the next group of defenders, and so
on, until either the invading force makes it all the way through the defenders or is completely routed.

Your goal is to determine whether or not a given invading force can make it through a particular gauntlet of defenders.

For the purposes of simplification, all defending strongholds in this simulation are considered to be in a straight line from the starting position of the
invaders, and must be encountered in order from nearest to furthest away. No strongholds will be in the same location in a given set of data.

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer E (1 ≤ E ≤ 20) indicating the number of defensive strongholds in the data set;
A series of E lines, each with three integers D, J, S (1 ≤ D, J ≤ 10000; 1 ≤ S ≤ 50) separated by spaces representing the strongholds. D is the
distance of the stronghold from the invaders’ starting position; remember that all strongholds are considered to be in a straight line from
the invaders’ starting position, and must be encountered in order from nearest to furthest away. J and S represent the strength of the
defenders and the stronghold, respectively, as in the above equation; and
A line containing a single integer I (1 ≤ I ≤ 30000) representing the strength of the invading force.

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer E (1 ≤ E ≤ 20) indicating the number of defensive strongholds in the data set;
A series of E lines, each with three integers D, J, S (1 ≤ D, J ≤ 10000; 1 ≤ S ≤ 50) separated by spaces representing the strongholds. D is the
distance of the stronghold from the invaders’ starting position; remember that all strongholds are considered to be in a straight line from
the invaders’ starting position, and must be encountered in order from nearest to furthest away. J and S represent the strength of the
defenders and the stronghold, respectively, as in the above equation; and
A line containing a single integer I (1 ≤ I ≤ 30000) representing the strength of the invading force.

2
1
10 10 5
100
2
75 100 5
10 10 5
50

ROUT!
RETREAT!

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢