Cleaning the Space
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A spacecraft is all set to travel through a long inter-galactic tunnel. The tunnel consists of N stationary space debris. In order to successfully complete the mission the spacecraft needs to destroy all the space debris. The control unit of the spacecraft has M buttons which can be used to destroy the space debris. Pressing a particular button may result in the destruction of some (possibly multiple) particular space debris. Once a space debris is destroyed its mass is converted into energy, which is eventually absorbed by the spacecraft in order to increase its speed. The amount of energy released from the disintegration of a particular space debris depends upon the button which has been used to destroy that space debris. A matrix E which contains this information is known as "Energy Vector". For each space debris i and each button j, E[i][j] is a positive integer between 0 and 100, which is the energy released after destroying space debris i using button j. The value of E[i][j] is -1 if space debris i cannot be destroyed using button j.
Some space debris have dependencies on other space debris in order to get destroyed. The spacecraft must destroy some specific space debris before causing the destruction of some other space debris. There are a total of K unique dependencies. Each dependency contains two space separated integers i and j, which denotes that the space debris i must be destroyed before destroying space debris j.
A particular button can be pressed only once and the buttons can be pressed only in order from 1 to M (ie. button 2 cannot be pressed before button 1 ). While pressing a specific button a binary string T of length N called as "Target Vector" is passed to the control unit of the spacecraft. For each space debris i, T[i] is 1 if you want to destroy that space debris with that button otherwiseT[i] is 0. When the button is pressed all the space debris mentioned in the Target Vector simultaneously gets destroyed.
The spacecraft may destroy any number of space debris using a particular button, including none, as long as they can be destroyed by that button and the spacecraft has already destroyed any required prerequisite space debris.
Now the task is to compute the maximum average energy that can be absorbed by the spacecraft throughout the entire mission.
- The first line of the input contains two space separated integers N and M.
- N lines follow, each containing M integers. The jth integer of the ith line represents the value of E[i][j].
- The next line contains an integer K.
- This is followed by K lines, each containing two space separated integers u and v, where u is never equal to v. it means that space debris u should be destroyed before space debris v
Outputprint a single real number which is the maximum average energy, rounded to two digits after the decimal point.
- 1 ≤ M, N ≤ 100
- 0 ≤ K ≤ 100
- -1 ≤ E[i][j] ≤ 100
- 1 ≤ u, v ≤ N
- It is guaranteed that there always exists a way to destroy N space debris using M buttons
Input: 3 3 10 70 100 80 50 40 80 20 40 2 1 2 1 3 Output: 50.00
One way the spacecraft can destroy the space debris is :
Destroy the first space debris by pressing the second button.
Destroy the second and third space debris using the third button.
The average energy is (70 + 40 + 40)/3 = 50.00, and this is optimal.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.