QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726803 | #8063. Seven Up | Broder | AC ✓ | 488ms | 1957116kb | C++23 | 2.0kb | 2024-11-09 08:53:28 | 2024-11-09 08:53:28 |
Judging History
answer
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(x) (long long)(x).size()
string deck;
double dp[78125][25][128];
int fivep[7];
int encode(char c) {
if (c=='A') return 0;
if (c=='2') return 1;
if (c=='3') return 2;
if (c=='4') return 3;
if (c=='5') return 4;
if (c=='6') return 5;
if (c=='7') return 6;
return 7;
}
double func(int key, int left, int available) {
// cout << key << ' ' << left << ' ' << available << endl;
if (available == 0) return 0;
if (left < 0) return 0;
if (dp[key][left][available] == -1) {
double p = 1;
double out = 0;
vector<double> cnt;
int temp = key;
double sum = left;
rep(i, 7) {
sum+=temp%5;
cnt.push_back(temp%5);
temp/=5;
}
rep(i, 7) {
if (cnt[i]==0) continue;
double pi = cnt[i]/sum;
int nxtKey = available;
int curr = i;
while (curr!=7 and nxtKey & (1<<curr)) {
nxtKey^=(1<<curr);
curr = encode(deck[curr]);
}
out+=pi*func(key-fivep[i], left, nxtKey);
p-=pi;
}
if (left!=0) out += p * func(key, left-1, available);
dp[key][left][available] = out+1;
}
return dp[key][left][available];
}
int main() {
rep (i, 78125) rep (j, 25) rep (k, 128) {
dp[i][j][k] = -1;
}
cin >> deck;
fivep[0] = 1;
rep(i, 6) {
fivep[i+1]=fivep[i]*5;
}
vector<int> cnt(7, 4);
int extra = 24;
rep(i, sz(deck)) {
if (encode(deck[i])!=7) {
cnt[encode(deck[i])]--;
}
else extra--;
}
int key = 0;
rep(i, 7){
key*=5;
key+=cnt[6-i];
}
cout << fixed << setprecision(10) << func(key, extra, (1<<7)-1) << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 219ms
memory: 1957068kb
input:
A9Q22T5
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'
Test #2:
score: 0
Accepted
time: 488ms
memory: 1956980kb
input:
JQQQKKK
output:
20.9131450564
result:
ok found '20.9131451', expected '20.9131451', error '0.0000000'
Test #3:
score: 0
Accepted
time: 227ms
memory: 1956924kb
input:
A234567
output:
25.1723868237
result:
ok found '25.1723868', expected '25.1723868', error '0.0000000'
Test #4:
score: 0
Accepted
time: 71ms
memory: 1956988kb
input:
234567A
output:
2.0909090909
result:
ok found '2.0909091', expected '2.0909091', error '0.0000000'
Test #5:
score: 0
Accepted
time: 87ms
memory: 1956988kb
input:
2356A74
output:
6.0475524476
result:
ok found '6.0475524', expected '6.0475524', error '0.0000000'
Test #6:
score: 0
Accepted
time: 131ms
memory: 1956832kb
input:
2A43657
output:
15.7540446396
result:
ok found '15.7540446', expected '15.7540446', error '0.0000000'
Test #7:
score: 0
Accepted
time: 140ms
memory: 1956952kb
input:
AAAA222
output:
18.9345686993
result:
ok found '18.9345687', expected '18.9345687', error '0.0000000'
Test #8:
score: 0
Accepted
time: 115ms
memory: 1957068kb
input:
274AA25
output:
13.2888888889
result:
ok found '13.2888889', expected '13.2888889', error '0.0000000'
Test #9:
score: 0
Accepted
time: 154ms
memory: 1956988kb
input:
7K7A598
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'
Test #10:
score: 0
Accepted
time: 131ms
memory: 1956952kb
input:
7K586T4
output:
15.8051282051
result:
ok found '15.8051282', expected '15.8051282', error '0.0000000'
Test #11:
score: 0
Accepted
time: 203ms
memory: 1957116kb
input:
9353K2T
output:
17.5812971342
result:
ok found '17.5812971', expected '17.5812971', error '0.0000000'
Test #12:
score: 0
Accepted
time: 274ms
memory: 1956960kb
input:
K59QKT3
output:
18.9345686993
result:
ok found '18.9345687', expected '18.9345687', error '0.0000000'
Test #13:
score: 0
Accepted
time: 224ms
memory: 1956984kb
input:
52Q2J68
output:
19.8812971342
result:
ok found '19.8812971', expected '19.8812971', error '0.0000000'