QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#277265 | #6565. Game Show Elimination | ucup-team1198# | AC ✓ | 362ms | 54744kb | C++14 | 4.5kb | 2023-12-06 17:10:05 | 2023-12-06 17:10:06 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int int64_t
const int MAXN = 1e3 + 10, MAXK = 11;
vector<double> p[1 << MAXK][MAXK];
vector<int> operator*(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size() - 1);
for (int i = 0; i < (int)a.size(); ++i) {
for (int j = 0; j < (int)b.size(); ++j) {
c[i + j] += a[i] * b[j];
}
}
return c;
}
vector<int> operator+(const vector<int>& a, const vector<int>& b) {
vector<int> c(max(a.size(), b.size()));
for (int i = 0; i < (int)a.size(); ++i) {
c[i] += a[i];
}
for (int i = 0; i < (int)b.size(); ++i) {
c[i] += b[i];
}
return c;
}
double dp[MAXN][1 << MAXK][MAXK];
double ans[MAXN];
signed main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
int n, k;
cin >> n >> k;
for (int mask = 0; mask < (1 << (k - 1)); ++mask) {
for (int d = 0; d < k; ++d) {
vector<int> a;
for (int i = 0; i < (k - 1); ++i) {
if (mask & (1 << i)) {
a.push_back(i);
}
}
a.push_back(k - 1);
a.push_back(k + d);
p[mask][d].resize(k + 1);
for (int i : a) {
for (int t = i; t < i + k; ++t) {
vector<int> prod = {1};
vector<int> sum = {0};
int cntk = 0;
for (int j : a) {
if (j == i) continue;
vector<int> up = {-j, 1};
vector<int> down = {j + k, -1};
++cntk;
if (t >= j + k) {
up = {1};
down = {0};
--cntk;
} else if (t + 1 <= j) {
up = {0};
down = {1};
--cntk;
}
sum = sum * up + prod * down;
prod = prod * up;
}
vector<double> intsum(sum.size() + 1);
for (int i = 1; i <= (int)sum.size(); ++i) {
intsum[i] = (double)sum[i - 1] / i;
for (int t = 0; t < cntk; ++t) {
intsum[i] /= k;
}
}
double vall = 0, valr = 0;
for (int i = (int)sum.size(); i >= 0; --i) {
vall = vall * t + intsum[i];
valr = valr * (t + 1) + intsum[i];
}
p[mask][d][min(i, k)] += (valr - vall) / k;
}
}
}
}
/// cerr << "p: " << p[0][0][1] << endl;
int mask0 = (1 << (k - 1)) - 1;
if (n - 2 < k - 1) {
mask0 = ((1 << (n - 2)) - 1) << (k - n + 1);
}
dp[n - 2][mask0][0] = 1;
/// cerr << mask0 << endl;
for (int mx2 = n - 2; mx2 >= 0; --mx2) {
for (int mask = (1 << (k - 1)) - 1; mask >= 0; --mask) {
int cnt = mx2 + 2;
for (int i = 0; i < (k - 1); ++i) {
if (mx2 - k + 1 + i < 0) continue;
if (!(mask & (1 << i))) {
--cnt;
}
}
int mx3 = mx2 - k;
for (int i = 0; i < (k - 1); ++i) {
if (mask & (1 << i)) {
mx3 = mx2 - k + 1 + i;
}
}
int start = mx3 - k + 1;
int mask1 = 0;
for (int i = start; i < mx3; ++i) {
if (i < 0) continue;
if (i <= mx2 - k) {
mask1 |= (1 << (i - start));
} else {
if (mask & (1 << (i - (mx2 - k + 1)))) {
mask1 |= (1 << (i - start));
}
}
}
for (int d = 0; d < k; ++d) {
for (int i = 0; i < (k - 1); ++i) {
if (mask & (1 << i)) {
dp[mx2][mask ^ (1 << i)][d] += dp[mx2][mask][d] * p[mask][d][i];
ans[mx2 - k + 1 + i] += dp[mx2][mask][d] * p[mask][d][i] * (cnt - 1);
}
}
ans[mx2] += dp[mx2][mask][d] * p[mask][d][k - 1] * (cnt - 1);
ans[mx2 + d + 1] += dp[mx2][mask][d] * p[mask][d][k] * (cnt - 1);
if (mx3 >= 0) {
dp[mx3][mask1][min(k - 1, mx2 + d + 1 - mx3 - 1)] += dp[mx2][mask][d] * p[mask][d][k - 1];
dp[mx3][mask1][min(k - 1, mx2 - mx3 - 1)] += dp[mx2][mask][d] * p[mask][d][k];
}
}
}
}
cout << fixed << setprecision(20);
for (int i = 0; i < n; ++i) {
cout << 1 + ans[i] << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5932kb
input:
3 2
output:
2.10937500000000000000 2.62500000000000000000 1.26562500000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 362ms
memory: 54744kb
input:
1000 10
output:
2.92729331661318248337 3.53731615687861156161 4.28118220331033150217 5.13122066019083966637 6.05393277902175963590 7.01918850987255815710 8.00570239911677461464 9.00129103035629007934 10.00016520768496874894 11.00000000001034017316 12.00000000001135980199 13.00000000001235278546 14.00000000001342037...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 33ms
memory: 11592kb
input:
300 8
output:
2.75126305133219561938 3.39007372705479870234 4.17500686507974982931 5.06602151944115064452 6.02014655784086905044 7.00455785889803195232 8.00057259306525736520 9.00000000000009414691 10.00000000000012079227 11.00000000000013145041 12.00000000000013500312 13.00000000000015631940 14.00000000000016520...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 5ms
memory: 12092kb
input:
1000 3
output:
2.23025616810293714209 3.03476567111320605363 3.99999999999999511502 4.99999999999999289457 5.99999999999999200639 6.99999999999999023004 7.99999999999998756550 8.99999999999998756550 9.99999999999998401279 10.99999999999998401279 11.99999999999998046007 12.99999999999998223643 13.999999999999978683...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 245ms
memory: 6968kb
input:
7 10
output:
2.98158643837177361746 3.49360496011804588790 3.96534226491272301374 4.31967705858751038761 4.50872485622269181249 4.49888084765053264391 4.23218357413660939415
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 121ms
memory: 30332kb
input:
993 9
output:
2.84112122851619508523 3.46435924464091105079 4.22732436744438011544 5.09694259816773787009 6.03528166580504343841 7.01057424280982743880 8.00238739423920009131 9.00030251838427020061 9.99999999999402078288 10.99999999999335464906 11.99999999999269739703 12.99999999999204369772 13.999999999991409538...
result:
ok 993 numbers