--- Day 2: An Explosive Diplomatic Crisis ---
You wake up to an emergency alarm inside your room at the Santa Claus Hotel. "Emergency. All residents must evacuate to the underground bunker immediately. The blast door will be sealed in five minutes."
Before you can put your pants on, an elf skids into your room. She has her hair in an imperfect bun and seems to be wearing a jacket two sizes too small.
"Move!" she says as she drags you towards the emergency stairwell. She gives you zero time to ask who she is, so you do the next best thing. You shout while being dragged.
"Okay! Who are you and what the hell is happening?"
"No time to explain, quick!" she pants. Which is a lie, because once you're shoved through a closing blast door and into the belly of the North Pole Base Emergency Command Centre, you get a long explanation of how her name is Patch and she works in human outreach and how she helped a human fix Christmas last December. As she's still talking about last christmas, you get the terrifying sight of Jingle, the head elf, coming out of a door.
"Right," says Jingle, looking as professional as an elf can be. "We have a problem. We just got intel that the next shipment of presents contain several bombs. Looks like someone's trying to attack us - perhaps due to our peace-negotiating efforts for wars. Anyway, thanks to our intel, we know exactly which presents are bombs and we know exactly the fuse length and blast radius of each of the bombs."
"What do you need me for then?" you are confused.
"Here's the thing, that shipment is coming in soon and we'll only have time to disarm one explosive present once it arrives. You'll have to choose one."
Patch taps a screen and an array of parcels pop up - each with a little icon, some are just a green circle - those are probably non-explosive, but many of them show a red hexagon with two numbers inside. You can already tell what they mean - fuse length and blast radius.
"We want as few presents destroyed as possible," says Jolly worriedly, "otherwise this will further escalate the diplomatic tension between countries, and all our efforts persuading them to make peace and exchange presents will have been in vain!"
Can you solve this bomb (and global diplomatic crisis) by figuring out which present the elves should disarm?
You are given a list of presents along with their properties (inert/explosive). For explosive presents, you are also given their radius and fuse time.
An explosive present explodes after its fuse time reaches 0, at which point all presents within its radius (including itself) are destroyed. A radius of 0 indicates that only the present itself is destroyed after it explodes. A radius of 1 indicates that presents on both its immediate left and right, along with the present itself, will be destroyed.
If an explosive present is destroyed by another explosive present, it will never explode, even after its fuse expires. If two presents in each other's radius have the same fuse, they explode simuiltaneously and do not prevent each other from exploding.
You may disarm one explosive present, and your job is to determine which present to disarm to minimise the number of presents destroyed after all explosive presents have exploded. Disarming a present does not destroy it.
The input file is in the following format:
N, the number of test cases.N lines contain the test cases. Each line contains a number of semicolon-separated gift descriptions. Each gift description can be in one of the following two formats:
inert, meaning the present is non-explosiveexplosive(a,b), meaning the present is explosive with radius a and fuse time b. Both a and b are integers.You should output a comma-separated list of N numbers, giving the 0-indexed present number you wish to disarm for each test case.
The input guarantees that there will always be at least one explosive present, and there is always a single optimal solution.
Sample Input:
1
explosive(2,3);inert;explosive(2,4);inert;inert;explosive(1,2)
Sample Output:
5
Explanation:
Therefore, the best present to disarm is the one at index 5, as it leaves the most possible number of presents intact.