Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:tips

Posted by forif at 2014-05-20 11:46:40 on Problem 3296 and last updated at 2014-05-20 11:49:37
In Reply To:tips Posted by:ragnarok01 at 2013-10-06 22:22:55
package poj;

import java.io.*;

public class POJ3296 {

//let xi be the amount of rain water to be used for i-th rinse and yi be the ratio of the whiskey to the total liquid after i-th rinse, then
//
//            Vw
//y1 = ----------------
//         x1 + Vw
//
//  	    y1 * Vr
//y2 = -----------------
//  	    x2 + Vr
//
//	.
//	.
//	.
//
//         y(n-1) * Vr
//yn = -------------------
//   	     xn + Vr
//
//     		  Vr^(n-1) * Vw
//   = ----------------------------------- (for i = 2 ... n)
//	     (x1 + Vw) * TT(xi + Vr)
//
//
//since Vr, Vw and n is all constant, we need the denominator be maximal in order to let the yn be minimal,
//when each part in denominator is strictly equals each other, the product should be maximal, that is
//x1 + Vw = xi + Vr		for i = 2 ... n
//==> x1 + Vw = (Vb - x1) / (k - 1) + Vr
//==> (k - 1) * x1 + (k - 1) * Vw = Vb - x1 + (k - 1) * Vr
//==> k * x1 = Vb + (k - 1) * Vr - (k - 1) * Vw
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out, false);
		
		while(true){
			String[] str = in.readLine().replaceAll("^ +", "").split(" +");
			while(str[0].equals(""))		str = in.readLine().replaceAll("^ +", "").split(" +");
			int k = Integer.parseInt(str[0]);
			if(k == 0)	break;
			double vb = Double.parseDouble(str[1]), vw = Double.parseDouble(str[2]), vr = Double.parseDouble(str[3]), vc = Double.parseDouble(str[4]);
			if(vb + vw < vr){
				out.println(0);
				continue;
			}
			
			double x1 = (vb + (k - 1) * vr - (k - 1) * vw) / k, xi = 0, left;
			if(x1 < 0)		x1 = 0;
			left = vb - (k - 1) * (vc - vr);
			if(x1 < left)		x1 = left;
			if(x1 + vw > vc)		x1 = vc - vw;
			if(x1 > vb)		x1 = vb;
			if(k > 1){
				xi = (vb - x1) / (k - 1);
				if(xi + vr > vc)	xi = vc - vr;
			}
			
			out.printf("%d %.2f", k, x1);
			for(int i = 1; i < k; i++)		out.printf(" %.2f", xi);
			out.println();
		}
		
		out.flush();
	}

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator