Woburn Challenge 2017-18 Finals Round - Senior Division
Problem 3: Explosive Ordinance Disposal
The Party of Extraterrestrial Gangsters has begun its invasion of Earth! Vast armies of PEG soldiers have been deployed down to the surface throughout Scarberia, and the cows and monkeys have engaged them in battle.
Amidst the fighting, however, the aliens have also transported something else to the planet's surface — a bomb with devastating nuclear power! All life in Scarberia, and perhaps the rest of Earth, would surely cease if the bomb were to detonate. Fortunately, the PEG leaders are honourable enough to give their enemies a fighting chance. As such, they've set the bomb to go off after a period of three hours, and implanted a system for defusing it. They've even included an instruction manual along with it!
On the surface of the bomb, there are N (1 ≤ N ≤ 200) electrical terminals. There are also N − 1 wires running amongst the terminals, the i-th of which runs between terminals Ai and Bi (1 ≤ Ai, Bi ≤ N), and is either black (if Ci = 0), or is otherwise white (if Ci = 1). The wires have been arranged such that all pairs of terminals are reachable from one another by following a sequence of wires.
Bo Vine and the Head-Monkey have gotten their hands on the bomb and its accompanying instruction manual. According to the manual, the bomb will turn itself off if the following conditions are all met:
- Each terminal i receives an electrical current with some voltage Vi, such that Vi is a positive integer.
- For each black wire i (such that Ci = 0), the greatest common divisor (GCD) of VAi and VBi is equal to 1.
- For each white wire i (such that Ci = 1), the GCD of VAi and VBi is greater than 1.
Bo Vine has ordered his cow engineers to prepare the necessary electrical equipment as quickly as possible. Meanwhile, the Head-Monkey has personally taken it upon herself to come up with a set of voltages V1..N which will successfully satisfy the conditions to defuse the bomb. However, having realized that PEG is essentially mocking them by dispatching a bomb which may be defused so easily, she's decided to get back at them by demonstrating the monkeys' superior intelligence and successfully defusing the bomb using as little voltage as possible. Help the Head-Monkey determine the minimum possible total voltage (sum of V1..N values) required to get the job done. Just make sure to figure it out within three hours!
In test cases worth 3/17 of the points, C1 = C2 = … = CN − 1.
The first line of input consists of a single integer, N.
N − 1 lines follow, the i-th of which consists of three space-separated integers, Ai, Bi, and Ci, for i = 1..(N − 1).
Output a single integer, the minimum possible total voltage required to defuse the bomb.
7 4 1 1 4 5 0 7 6 1 3 6 1 1 7 0 2 4 1
It's optimal to send
- a 1-volt current to terminal 5;
- 2-volt currents to terminals 1, 2, and 4; and
- 3-volt currents to terminals 3, 6, and 7.
Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: May 13, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3