11109 - Rinse

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11109 - Rinse

Post by Khaled_912 »

Any ideas how to approach this problem?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by Khaled_912 »

Thanks for your... uhh.. *cool* hint :D 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

Post by 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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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

Post by Khaled_912 »

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:

Post by 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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post by 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 ??

Post Reply

Return to “Volume 111 (11100-11199)”