To read or not to read P47959


pdf   zip


The Great Masao has to read a lot to learn all he needs for his new job, so he has n boxes (numbered 0 …n − 1) full of books. Every box i is labelled with a number ki, which is the increment of knowlegde achieved after reading any of the books in i. But be aware: reading some books can decrease your knowledge!

A box x can be a prerequisite of another box y. In this case, before Masao can read one or more books from box y, he must have read at least one book from box x.

Masao will do t times:

  • Choose a box i at random.
  • If he can read one of the books of i (this will depend on the prerequisites) and if he decides to do so, he will read a book from i, thus adding ki to his knowledge.

At every step, Masao will always take an optimal decision (to read or not to read). What is the maximum expected amount of knowledge that Masao can gain?


Input is all integers, and consists of several cases. Every case begins with t, n, and the number of prerequisites p. Follow the n increments ki (each is an integer number with absolute value at most 106). Follow p different pairs of x and y (with xy), indicating that x is a prerequisite of y. Books are numbered starting at zero. You can assume 0 ≤ t ≤ 50 and 1 ≤ n ≤ 10.


For every case, print with two digits after the decimal point which is the maximum expected increment of knowledge of the Great Masao. The input cases have no precision issues.

Public test cases
  • Input

    1 2 0
    30 60
    50 10 0
    1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
    17 6 5
    1000 -100 -100 -100 -100 -100
    1 0   2 0   3 0   4 0   5 0


  • Information
    Xavier Martínez
    Official solutions
    User solutions