11109 - Rinse

[Khaled_912]

Any ideas how to approach this problem?

[rio]

Hint:
Input:

Code: Select all

2 15.0 25.0 32.0 50.0
3 15.0 8.0 3.0 10.0
0

Output:

Code: Select all

2 11.00 4.00
3 1.67 6.67 6.67

[Khaled_912]

Thanks for your... uhh.. *cool* hint It made me realize that my old greedy solution wasn't correct.
It came to my mind to use ternary search, but I ended up getting WA (but your test data matched). Please see if you can post some more test cases.

[rio]

Hint:
Input:

Code: Select all

3 24.0 8.0 3.0 10.0
2 1.0 1.0 4.0 10.0
1 3.0 1.0 2.0 5.0
0

Output:

Code: Select all

3 2.00 7.00 7.00
0
1 3.00

[Khaled_912]

Still WA...
Correct me if I'm wrong, but I assume that all rinses use the same amount of water... except the first rinse which I use ternary search to calculate.

[rio]

I think you don't need search. Atlesat, I didn't use.

[Khaled_912]

but is the assumption that from the 2nd uptill the Kth rinse will use the same amount of water correct?

[Erik]

Hello,

but is the assumption that from the 2nd uptill the Kth rinse will use the same amount of water correct?

Yes, this is correct.
With some analysis search is not necessary.

Cu, Erik

[Khaled_912]

I think I totally failed to do the analysis, even after I found the source code which distributes the average value of (vb+vw-vr)/k, I didn't understand why this is correct. Any explanation plz ??