[Solution] Training Plans solution codechef

Training Plans solution codechef – Nathan is preparing for the Dash marathon. He has NN training plans. The ii-th plan has an effectiveness of AiAi, but requires that at least BiBi other training plans must be performed before it. A training plan cannot be repeated.

Training Plans solution codechef

If he performs some K>0K>0 distinct trainings – P1,P2,,PKP1,P2,…,PK (1PiN,PiPj)(1≤Pi≤N,Pi≠Pj) then his training score is Kj=1APjK∑j=1KAPjK. If Nathan does not perform any training plan (K=0)(K=0), then his score is 00.

What is the highest score that Nathan can get by performing zero or more training plans, if he can perform them in any order?

Input Format

  • The first line of the input contains a single integer TT – the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains NN – the number of training plans.
  • The second line contains NN integers A1,A2,,ANA1,A2,…,AN where AiAi is the effectiveness of the ii-th training plan.
  • The third line contains NN integers B1,B2,,BNB1,B2,…,BN where BiBi is the number of pre-requisite training plans for the ii-th training plan.

Output Format

  • For each test case, output a single real number – the highest score that Nathan can get by performing zero or more training plans.
  • Your answer is considered correct if its absolute or relative error does not exceed 10610−6. Formally, let your answer be XX, and the jury’s answer be YY. Your answer is accepted if and only if |XY|max(1,|Y|)106|X−Y|max(1,|Y|)≤10−6.

Training Plans solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 105Ai105−105≤Ai≤105
  • 0BiN10≤Bi≤N−1
  • Sum of NN over all test cases does not exceed 51055⋅105.

Sample Input 1 

3
4
-9 -21 -4 -43
0 0 0 0
5
10 14 5 9 1
4 1 3 0 0
7
-1 101 5 63 -7 -88 59
0 1 6 2 3 4 5

Sample Output 1 

0.000000
11.500000
54.333333

Training Plans solution codechef Explanation

Test case 1: It is optimal for Nathan to not perform any training plans as all the plans have negative AiAi value.

Test case 2: It is optimal for Nathan to:

  • First, perform the 44-th training plan (for which Bi=0Bi=0).
  • Then perform the 22-nd training plan (for which Bi=1Bi=1 which is satisfied as he has already performed 11 training plan)

Test case 3: It is optimal for Nathan to:

  • First, perform the 11-st training plan (for which Bi=0Bi=0).
  • Then perform the 22-nd training plan (for which Bi=1Bi=1 which is satisfied as he has already performed 11 training plan)
  • Then perform the 44-th training plan (for which Bi=2Bi=2 which is satisfied as he has already performed 22 training plans)

Leave a Comment