GCJ2012 Round1B A. Safety in Numbers

2012-05-06

14:37 |

S[i] が与えられる。0<=Y[i]<=1 として、各 i について F[i] = S[i]+(ΣS)*Y[i] が単独で最小にならないようにするための Y[i] の最小値を求める問題。

Y[i] が決まると F[i] が決まって、i!=j な F[j] が F[i] 以下になればいいので
Y[j] として最低必要な分を 1-Y[i] から補充していく。
全部補充できたら F[i] は単独で最小にならない。
各 i について Y[i] を 0～1 の間で二分探索する。

max(0, A-w[j]) の和 < 1-Y[i] かどうかだけ判定したほうがスマートだった

int f(int i, double mid, VI& w, int N, int sum) {
	double A = w[i]+sum*mid;
	double rest = sum*(1-mid);
	int ok=1;
	REP(j, N) {
		if(i==j) continue;
		if(A>w[j]) {
			rest -= A-w[j];
			if(rest<0) {
				ok=0;
				break;
			}
		}
	}
	return ok;
}

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int N;
		cin>>N;
		VI w(N);
		REP(i, N) cin>>w[i];
		int sum = accumulate(ALL(w), 0);
		
		cout<<"Case #"<<ttt+1<<": ";
		REP(i, N) {
			if(i!=0) cout<<" ";
			double lo = 0, hi = 1;
			REP(loop, 100) {
				double mid = (lo+hi)/2;
				//cout<<mid<<" "<<A<<" "<<ok<<endl;
				int ok = f(i, mid, w, N, sum);
				if(ok) lo=mid;
				else   hi=mid;
			}
			cout<<setprecision(8)<<hi*100;
		}
		cout<<endl;
	}
	return 0;
}