ApocalypseEasy
SRM 721 · 2017-08-30 · by cgy4ever
Problem Statement
There are k tokens on the tree, each in a different node. You are given a
A demon has placed k bombs onto the tree: one bomb into each node that currently contains a token. The bombs will all explode after t turns. If there is a token in a node with a bomb when the bomb explodes, the token is destroyed. Your task is to save as many tokens as possible.
In each turn you can move each token at most once: from its current node to any adjacent node. During the turns each node may temporarily contain arbitrarily many tokens, even at the end of a turn. (See Example 4.) There is only one constraint: at the very end of the whole process (i.e., after turn t) each node must again contain at most one token.
Compute and return the maximal number of tokens saved from the explosions.
Constraints
- n will be between 2 and 50, inclusive.
- p will contain exactly n-1 elements.
- For each i, 0 <= p[i] <= i.
- position will contain between 1 and n elements, inclusive.
- Each element in position will be between 0 and n-1, inclusive.
- Elements in position will be distinct.
- t will be between 1 and 50, inclusive.
{0,1,2}
{2,3}
1
Returns: 1
The tree is a line: 0 - 1 - 2 - 3. Initially, the tokens and the bombs are in the nodes 2 and 3. We have only one turn. Whatever we do, the token that starts on node 3 will be destroyed. We can save the other token by moving it from node 2 to node 1.
{0,1,2}
{2,3}
2
Returns: 2
This is the same setting as in Example 0, but now we have two turns. Now we can save both tokens. In the first turn we move the token from node 2 to node 1 and the token from node 3 to node 2. In the second turn we move the two tokens from 1 to 0 and from 2 to 1.
{0,0,0,1,2,3}
{1,2,3}
1
Returns: 3
{0,1,2,3,4,5,6,7,8,9}
{0,1,2,3,4,5,6}
50
Returns: 4
{0,0,0,0,0}
{0,1,2}
2
Returns: 3
This tree is a star: each of the nodes 1 through 5 is connected to node 0. Initially, nodes 0, 1, and 2 contain the tokens. We have two turns. One optimal solution looks as follows: In the first turn we move the tokens from nodes 1 and 2 into node 0. Thus, after the first turn all three tokens are in node 0. In the second turn we move the three tokens into the nodes 3, 4, and 5, respectively. Thus, we managed to save all three tokens.
Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ApocalypseEasy with a public method int maximalSurvival(vector<int> p, vector<int> position, int t) · 108 test cases · 2 s / 256 MB per case