| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14532 | Elephants, cats and bugs |
|
| 14533 | Merging for migration |
|
Description
We all know the concept of food chain in nature, and there is a similar situation in NTHU - The counter cycle among elephants, cats, and bugs (don’t worry, elephants won’t eat cats). These three species engage in battles on campus, the rules are as follows.
- Normal attack: If the attacker and the defender are not of the same species, and the attacker does not counter the defender, the damage dealt will be the attacker's attack power minus the defender's defense power.
- Counter attack: If the attacker and the defender are not of the same species, and the attacker counters the defender, the attacker’s attack power is doubled during that fight. The defender then takes damage equal to the new attack power minus its defense power.
- Heal magic: If the attacker and the defender are of the same species, the attack is converted into healing magic, and the defender recovers HP equal to the attacker’s attack power.
The counter relationship:
- Elephants counter cats
- Cats counter bugs
- Bugs counter elephant
Once a contestant is dead (HP = 0), it cannot attack, heal, or revive anymore (but you still have to output the result of battle).
All attacks will not deal negative damage, and the minimum HP is 0.
There are n contestants and q battles. Please output the remaining HP of the defender after each battle.
This is a partial judge problem. You only need to implement battle() function.
The illustrations below is the demostration of the sample case.
Input
The first line contains two integers, n and q.
2 ≤ n, q ≤ 1000
The following n lines each line contain a string and three integers s, hp, atk and def, representing the species, health point, attack power and defend power of i-th (1-based) contestant, respectively.
s belong to {"Elephant", "Cat", "Bug"}
1 ≤ hp ≤ 1000
1 ≤ atk, def ≤ 300
The following q lines each line contain two distinct integers a and b, representing the index of the attcker and the defender.
1 ≤ a, b ≤ n
Output
Output the remain HP of the defender, followed by a new line character '\n';
Sample Input Download
Sample Output Download
Partial Judge Code
14532.cPartial Judge Header
14532.hTags
Discuss
Description
Elephants form two types of formations during migration:
- Sorted by Age: Ensures that older elephants can correctly lead the group to their destination.
- Sorted by Height: Ensures that elephants at the rear can see every elephant in front of them.
Elephants prefer using merge sort. Please help them sort by age and height separately and print the results. If there are identical values while sorting, the original relative order of index should be preserved (stable sort).
This is a partial judge problem. You only need to implement merge_by_age() and merge_by height() functions, the output function has already been provided for you.
Input
The first line contains a single integer n - the number of elephants.
2 ≤ n ≤ 105
The following n lines each line contain two integer a, h - the age and height of i-th elephant.
1 ≤ a, h ≤ 109
(Elephants are tall and long-lived animals.)
Output
Output the result of the index in each merge section, the format has already been implemented in the given function.