結果

問題 No.3318 客に卵をかける
コンテスト
ユーザー Andrew8128
提出日時 2025-10-26 10:33:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4,129 ms / 2,000 ms
コード長 1,895 bytes
コンパイル時間 2,516 ms
コンパイル使用メモリ 277,168 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-28 20:49:01
合計ジャッジ時間 13,272 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
long N, X, Y;
__float128 P, Q, R;
// 通常業務remain回のうち、クビになる選択をx回行うときの期待値
__float128 f(long x, long remain, __float128 p)
{
	__float128 a = (remain - x) * (Q - (1.0 - p) * R);	// もみ消す
	__float128 b = Q * ((1.0 - pow(p, x)) / (1.0 - p)); // クビになる
	return a + b;
}
// クビになる選択をする回数をx回からx+1回に変更したときの差分を求める
__float128 g(long x, long remain, __float128 p)
{
	__float128 a = -Q + (1 - p) * R;
	__float128 b = Q * pow(p, x);
	return a + b;
}
// 通常業務をt回行う時の最適値を求める
__float128 h(long t)
{
	long skill = X + t * Y;
	__float128 p = 1.0 - 1.0 / skill;
	long remain = N - t;
	if (skill == 1) // 卵をかけてしまう確率が100%のとき
	{
		return P * t + max((__float128)0.0, Q - R) * (remain - 1) + Q;
	}
	long left = 0, right = remain;
	while (1 < right - left)
	{
		long mid = (left + right) / 2;
		if (g(mid, remain, p) < 0)
		{
			right = mid;
		}
		else
		{
			left = mid;
		}
	}
	return P * t + f(right, remain, p);
}
int main(void)
{
	auto solve = []()
	{
		cin >> N;
		cin >> X >> Y;
		{
			double p, q, r;
			cin >> p >> q >> r;
			P = p, Q = q, R = r;
		}
		long l = 0, r = N;
		while (r - l > 10)
		{
			long m1 = l + (r - l) / 3;
			long m2 = r - (r - l) / 3;
			__float128 v1 = h(m1);
			__float128 v2 = h(m2);
			if (v1 < v2)
			{
				l = m1;
			}
			else
			{
				r = m2;
			}
		}
		__float128 ans = 0;
		for (long t = l; t <= r; ++t)
		{
			ans = max(ans, h(t));
		}
		__int128 a = ans * 100'000'000'000.0;
		long b = a / (__int128(100'000'000'000L));
		long c = a % (__int128(100'000'000'000L));
		c = (c + 5) / 10;
		if (c == 10'000'000'000L)
		{
			c = 0;
			b += 1;
		}
		printf("%ld.%010ld\n", b, c);
	};
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		solve();
	}
}
0