結果
問題 |
No.2158 X日後に全完するhibit君
|
ユーザー |
![]() |
提出日時 | 2022-12-09 23:50:24 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,787 bytes |
コンパイル時間 | 505 ms |
コンパイル使用メモリ | 31,872 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-14 23:11:57 |
合計ジャッジ時間 | 1,124 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <stdio.h> int main () { int n = 0; int k = 0; int p[6] = {}; int s[6] = {}; int t[6] = {}; int res = 0; double ans = 0.0; int sum_s = 0; int sum_t = 0; double prob[22][5000] = {}; int min = 22; int max = 0; res = scanf("%d", &n); res = scanf("%d", &k); for (int i = 0; i < n; i++) { res = scanf("%d", p+i); res = scanf("%d", s+i); res = scanf("%d", t+i); sum_s += s[i]; sum_t += t[i]; } if (sum_s <= 60) { printf("1 1 1\n"); return 0; } if (sum_t > 60) { printf("-1\n"); return 0; } prob[k+1][0] = 1.0; for (int i = k+1; i < 21; i++) { for (int j = 0; j < (1<<(2*n)); j++) { if (prob[i][j] > 0.0) { int num[6] = {}; for (int l = 0; l < n; l++) { num[l] = (j>>(l*2))%4+1; } for (int l = 0; l < (1<<n); l++) { int sum_st = 0; int mul = 1; int div = 1; double tmp_prob = prob[i][j]; int nxt = 0; for (int q = 0; q < n; q++) { if ((l&(1<<q)) > 0) { sum_st += t[q]; mul *= num[q]; nxt += ((num[q]-1)<<(2*q)); } else { sum_st += s[q]; mul *= p[q]-k-num[q]; nxt += ((num[q])<<(2*q)); } div *= p[q]-k; } tmp_prob *= ((double)mul)/((double)div); if (sum_st > 60) { prob[i+1][nxt] += tmp_prob; } else { ans += tmp_prob*((double)(i+1)); if (min > i+1) { min = i+1; } if (max < i+1) { max = i+1; } } } } } } printf("%d %d %.16lf\n", min, max, ans); return 0; }