## 11109 - Rinse

Moderator: Board moderators

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

### 11109 - Rinse

Any ideas how to approach this problem?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I think you don't need search. Atlesat, I didn't use.

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
but is the assumption that from the 2nd uptill the Kth rinse will use the same amount of water correct?

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm
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 ??