QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122127 | #6565. Game Show Elimination | tacoref | AC ✓ | 805ms | 48884kb | C++14 | 5.1kb | 2023-07-09 15:13:12 | 2023-07-09 15:13:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rng(i, b, e) for (int i = (b); i <= (e); i++)
#define rep(i, k) rng(i, 0, k - 1)
#define gnr(i, e, b) for (int i = (e); i >= (b); i--)
#define per(i, k) gnr(i, k - 1, 0)
#define fi first
#define se second
#define pb push_back
#define vc vector
#define si(x) (int)(x.size())
using vi = vector<int>;
using ll = long long;
using pll = pair<ll, ll>;
map<char, int> Map;
double P[1 << 10][12][12], Pr[12];
int PC[1 << 10][12];
int n, K;
double Over(int a, int b) {
if (abs(a - b) >= K) {
if (a > b)
return 1.0;
return 0.0;
}
if (a > b)
return 1 - Pr[a - b];
return Pr[b - a];
}
using vd = vector<double>;
vd Mul(vd A, int t) { // (x+t)/K
int m = si(A);
vd res(m + 1);
rep(i, m) {
res[i] += A[i] * t / K;
res[i + 1] += A[i] / K;
}
return res;
}
double res[1100];
vd Integral(vd A) {
int m = si(A);
vd res(m + 1);
rep(i, m) { res[i + 1] += A[i] / (i + 1); }
return res;
}
double Calc(int a, int M, vi T) {
double ans = 0.0;
rep(i, K) {
int b = a + i, e = a + i + 1;
int ck = 0;
if (M + K <= b)
continue;
vd U;
U.pb({1.0});
for (auto &t : T) {
if (t >= e) {
ck = 1;
break;
}
if (t + K <= b) {
continue;
}
// b ~b + 1 t ~t + K
// Prob: (x + b - t) / K
U = Mul(U, b - t);
}
if (ck == 1)
continue;
if (M < e) {
auto UU = Mul(U, b - M);
vc<double> ZZ(si(U) + 1);
rep(i, si(U) + 1) {
ZZ[i] = -UU[i];
if (i < si(U))
ZZ[i] += U[i];
}
U = ZZ;
}
U = Integral(U);
double tt = 0.0;
for (auto &t : U)
tt += t;
ans += tt / K;
}
/* printf("========\n%d\n", a);
printf("%d\n", M);
for (auto &t : T)
printf("%d ", t);
puts("");
printf("%.10f\n", ans);
puts("=======");*/
return ans;
}
double D[1010][1 << 9][11];
int main() {
scanf("%d%d", &n, &K);
if(K==1){
rng(i,1,n){
}
}
rng(i, 0, K) { Pr[i] = 0.5 * (K - i) * (K - i) / (K * K); }
rep(i, (1 << K)) {
rng(j, 0, K) {
vi V;
rep(k, K) {
if ((i >> k) & 1)
V.pb(k);
}
V.pb(K + j);
int m = si(V);
if (m < 2)
continue;
PC[i][j] = m;
rep(k, m) {
rep(pv, m) {
if (pv == k)
continue;
vi Z;
rep(l, m) {
if (l != pv && l != k) {
Z.pb(V[l]);
}
}
P[i][j][k] += Calc(V[k], V[pv], Z);
}
// printf("%d %d %d: %.10f\n", i, j, k, P[i][j][k]);
}
}
}
D[n][0][0] = 1;
gnr(i, n, 0) {
per(j, (1 << (K - 1))) {
gnr(k, K, 0) {
//printf("%d %d %d: %f\n", i, j, k, D[i][j][k]);
if (D[i][j][k] < 1e-20)
continue;
int cnt = i;
vi TP;
rep(l, K - 1) {
if ((j >> l) & 1){
TP.pb(i + 1 + l);
cnt++;
}
}
int rem = -1;
if (k) {
cnt++;
rem = i + K - 1 + k;
TP.pb(i + K - 1 + k);
}
gnr(l, i - 1, i - 2) {
if (l >= 0)
TP.pb(l);
}
sort(all(TP));
assert(!TP.empty());
if (si(TP) == 1) { // only one left
if (k!=K) {
//printf("%d %f\n",TP[0], D[i][j][k]);
res[TP[0]] += D[i][j][k];
}
continue;
}
int mid = TP[si(TP) - 2], ee = TP.back();
int s = 0;
vi V;
rng(l, mid - K + 1, mid) {
if (l < 0)
continue;
if (l >= i + 1 && ((j >> (l - i - 1)) & 1)) {
s += (1 << (l - (mid - K + 1)));
V.pb(l);
}
if (l < i) {
s += (1 << (l - (mid - K + 1)));
V.pb(l);
}
}
V.pb(ee);
int x = s, y = min(ee - mid - 1, K);
int z = PC[x][y];
//printf("cnt: %d\n",cnt);
rep(l, z) {
double p = P[x][y][l];
//printf("prob %d %d %d: %f\n", x, y, l, p);
if (p < 1e-12)
continue;
if (V[l] > i) {
int pv = V[l];
if (V[l] == rem) {
//printf("%.10f %d %d\n", D[i][j][k] * p * cnt,k,K);
assert(k!=K);
assert(pv >= i+K);
res[V[l]] += D[i][j][k] * p * cnt;
//printf("%d %.10f\n",V[l],D[i][j][k] * p* cnt);
D[i][j][0] += D[i][j][k] * p;
} else {
res[V[l]] += D[i][j][k] * p * cnt;
//printf("%d %.10f\n",V[l],D[i][j][k] * p* cnt);
D[i][j ^ (1 << (pv - i - 1))][k] += D[i][j][k] * p;
}
} else {
int pv = V[l];
int nrem = -1;
int ns = 0;
int nrori;
for (auto &t : V) {
if (t == pv)
continue;
if (t > pv) {
if (t >= pv + K) {
nrem = t - pv - K + 1;
nrori = t;
} else {
ns += (1 << (t - pv - 1));
}
}
}
if (nrem == -1)
nrem = 0;
// printf("%d %d %d %f %f\n", pv, ns, nrem, D[i][j][k], p);
//printf("%d %.10f\n",pv,D[i][j][k] * p* cnt);
res[pv] += D[i][j][k] * p* cnt;
if (nrem >= K && k < K) {
//printf("?? %d %.10f\n",nrori, D[i][j][k] * p);
res[nrori] += D[i][j][k] * p;
}
D[pv][ns][min(nrem,K)] += D[i][j][k] * p;
}
}
}
}
}
rep(i,n)printf("%.10f\n",res[i]);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5720kb
input:
3 2
output:
2.1093750000 2.6250000000 1.2656250000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 805ms
memory: 48884kb
input:
1000 10
output:
2.9272933166 3.5373161569 4.2811822033 5.1312206602 6.0539327790 7.0191885099 8.0057023991 9.0012910303 10.0001652077 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 23.0000000000 ...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 84ms
memory: 11068kb
input:
300 8
output:
2.7512630513 3.3900737271 4.1750068651 5.0660215194 6.0201465578 7.0045578589 8.0005725931 9.0000000000 10.0000000000 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 23.0000000000 ...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 7672kb
input:
1000 3
output:
2.2302561681 3.0347656711 4.0000000000 5.0000000000 6.0000000000 7.0000000000 8.0000000000 9.0000000000 10.0000000000 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 23.0000000000 ...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 367ms
memory: 4884kb
input:
7 10
output:
2.9815864384 3.4936049601 3.9653422649 4.3196770586 4.5087248562 4.4988808477 4.2321835741
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 294ms
memory: 29348kb
input:
993 9
output:
2.8411212285 3.4643592446 4.2273243674 5.0969425982 6.0352816658 7.0105742428 8.0023873942 9.0003025184 10.0000000000 11.0000000000 12.0000000000 13.0000000000 14.0000000000 15.0000000000 16.0000000000 17.0000000000 18.0000000000 19.0000000000 20.0000000000 21.0000000000 22.0000000000 23.0000000000 ...
result:
ok 993 numbers