/*#define DEBUG*/ #include #include typedef struct { char name[5]; int numb; int rank; int tot_win, tot_dif, tot_gol; int eac_win, eac_dif, eac_gol; } team_t; team_t team[5]; team_t backup_team[5]; int score[4][4]; int target; int undec[4][2]; int n_undec; double pt[9]; int is_recursed; int global_tie[2][2]; int global_ties; void sort_eac_win(int from, int to); void print() { int i; for (i = 0; i < 4; i++) { printf("%d(%d) ", team[i].numb, team[i].rank); } printf("\n"); } void print_score() { int i, j; for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) { if (i == j) printf("- "); else printf("%d ", score[i][j]); } printf("\n"); } } int sub_mkpt(int n) { int r, i; r = 1; for (i = 2; i <= 8; i++) r *= i; for (i = 2; i <= n; i++) r /= i; for (i = 2; i <= 8 - n; i++) r /= i; return r; } void mkpt() { int i; double b; for (i = 0; i <= 8; i++) { pt[i] = pow(0.25, (double)i) * pow(0.75, (double)(8 - i)) * (double)sub_mkpt(i); } } void input() { int i, j; char s[100]; n_undec = 0; gets(s); for (i = 0; i < 4; i++) { if (s[(i+1)*5+0] == '*') target = i; team[i].name[0] = s[(i+1)*5+1]; team[i].name[1] = s[(i+1)*5+2]; team[i].name[2] = s[(i+1)*5+3]; team[i].name[3] = 0; } for (i = 0; i < 4; i++) { gets(s); for (j = 0; j < 4; j++) { if (j <= i) continue; if (s[(j+1)*5+1] == '_') { undec[n_undec][0] = i; undec[n_undec][1] = j; n_undec++; } else { score[i][j] = s[(j+1)*5+1] - '0'; } if (s[(j+1)*5+3] == '_') { undec[n_undec][0] = j; undec[n_undec][1] = i; n_undec++; } else { score[j][i] = s[(j+1)*5+3] - '0'; } } } } /* score 完成後実行 */ void mkteamdata() { int i, j; /* 番兵 */ strcpy(team[4].name, "***"); team[4].numb = 4; team[4].tot_win = team[4].tot_dif = team[4].tot_gol = team[4].eac_win = team[4].eac_dif = team[4].eac_gol = -9999; for (i = 0; i < 4; i++) { team[i].numb = i; team[i].rank = 9999; team[i].tot_win = team[i].tot_dif = team[i].tot_gol = 0; for (j = 0; j < 4; j++) { if (score[i][j] > score[j][i]) team[i].tot_win += 3; else if (score[i][j] == score[j][i]) team[i].tot_win++; team[i].tot_dif += score[i][j] - score[j][i]; team[i].tot_gol += score[i][j]; } } } void mkeac_win(int from, int to) { int i, j; for (i = from; i <= to; i++) { team[i].eac_win = 0; for (j = from; j <= to; j++) { if (i == j) continue; if (score[team[i].numb][team[j].numb] > score[team[j].numb][team[i].numb]) { team[i].eac_win += 3; } else if (score[team[i].numb][team[j].numb] == score[team[j].numb][team[i].numb]) { (team[i].eac_win)++; } } } } void mkeac_dif(int from, int to) { int i, j; for (i = from; i <= to; i++) { team[i].eac_dif = 0; for (j = from; j <= to; j++) { if (i == j) continue; team[i].eac_dif += score[team[i].numb][team[j].numb] - score[team[j].numb][team[i].numb]; } } } void mkeac_gol(int from, int to) { int i, j; for (i = from; i <= to; i++) { team[i].eac_gol = 0; for (j = from; j <= to; j++) { if (i == j) continue; team[i].eac_gol += score[team[i].numb][team[j].numb]; } } } /* =========================================================================*/ int equals(const team_t a, const team_t b) { if (a.numb != b.numb || a.rank != b.rank || a.tot_win != b.tot_win || a.tot_dif != b.tot_dif || a.tot_gol != b.tot_gol || a.eac_win != b.eac_win || a.eac_dif != b.eac_dif || a.eac_gol != b.eac_gol) { return 0; } return 1; } void team_copy(team_t *a, team_t b) { a->numb = b.numb; a->rank = b.rank; a->tot_win = b.tot_win; a->tot_dif = b.tot_dif; a->tot_gol = b.tot_gol; a->eac_win = b.eac_win; a->eac_dif = b.eac_dif; a->eac_gol = b.eac_gol; } /* =========================================================================*/ int cmp_eac_gol(const team_t *a, const team_t *b) { if (a->eac_gol > b->eac_gol) return -1; else if (a->eac_gol == b->eac_gol) return 0; return 1; } void sort_eac_gol(int from, int to) { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; team_t temp_team; /* Making eac_gol data */ mkeac_gol(from, to); /* Backup */ team_copy(&temp_team, team[to + 1]); team[to + 1].eac_gol = -9998; qsort(&(team[from]), to - from + 1, sizeof(team_t), cmp_eac_gol); for (i = from; i <= to + 1; i++) { if (temp == team[i].eac_gol) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].eac_gol; } /* Restore */ team_copy(&(team[to + 1]), temp_team); if (is_recursed) { for (i = 0; i < 4; i++) { if (!equals(team[i], backup_team[i])) { goto recurse; } } return; } else { /* まだ一回も再帰してなければ問答無用で一回は再帰 */ goto recurse; } recurse: is_recursed = 1; /* 一回は再帰した */ for (i = 0; i < 4; i++) { team_copy(&(backup_team[i]), team[i]); } for (i = 0; i < ties; i++) { sort_eac_win(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ int cmp_eac_dif(const team_t *a, const team_t *b) { if (a->eac_dif > b->eac_dif) return -1; else if (a->eac_dif == b->eac_dif) return 0; return 1; } void sort_eac_dif(int from, int to) { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; team_t temp_team; /* Making eac_dif data */ mkeac_dif(from, to); /* Backup */ team_copy(&temp_team, team[to + 1]); team[to + 1].eac_dif = -9998; qsort(&(team[from]), to - from + 1, sizeof(team_t), cmp_eac_dif); for (i = from; i <= to + 1; i++) { if (temp == team[i].eac_dif) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].eac_dif; } /* Restore */ team_copy(&(team[to + 1]), temp_team); for (i = 0; i < ties; i++) { #ifdef DEBUG printf("(5) > %d - %d\n", tie[i][0], tie[i][0] + tie[i][1] - 1); printf("(5)>> "); print(); #endif sort_eac_gol(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ int cmp_eac_win(const team_t *a, const team_t *b) { if (a->eac_win > b->eac_win) return -1; else if (a->eac_win == b->eac_win) return 0; return 1; } void sort_eac_win(int from, int to) { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; team_t temp_team; /* Making eac_win data */ mkeac_win(from, to); /* Backup */ team_copy(&temp_team, team[to + 1]); team[to + 1].eac_win = -9998; qsort(&(team[from]), to - from + 1, sizeof(team_t), cmp_eac_win); for (i = from; i <= to + 1; i++) { if (temp == team[i].eac_win) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].eac_win; } /* Restore */ team_copy(&(team[to + 1]), temp_team); for (i = 0; i < ties; i++) { #ifdef DEBUG printf("(4) > %d - %d\n", tie[i][0], tie[i][0] + tie[i][1] - 1); printf("(4)>> "); print(); #endif sort_eac_dif(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ int cmp_tot_gol(const team_t *a, const team_t *b) { if (a->tot_gol > b->tot_gol) return -1; else if (a->tot_gol == b->tot_gol) return 0; return 1; } void sort_tot_gol(int from, int to) { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; team_t temp_team; /* Backup */ temp_team = team[to + 1]; team[to + 1].tot_gol = -9999; qsort(&(team[from]), to - from + 1, sizeof(team_t), cmp_tot_gol); for (i = from; i <= to + 1; i++) { if (temp == team[i].tot_gol) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].tot_gol; } /* Restore */ team[to + 1] = temp_team; for (i = 0; i < ties; i++) { #ifdef DEBUG printf("(3) > %d - %d\n", tie[i][0], tie[i][0] + tie[i][1] - 1); printf("(3)>> "); print(); #endif sort_eac_win(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ int cmp_tot_dif(const team_t *a, const team_t *b) { if (a->tot_dif > b->tot_dif) return -1; else if (a->tot_dif == b->tot_dif) return 0; return 1; } void sort_tot_dif(int from, int to) { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; team_t temp_team; /* Backup */ temp_team = team[to + 1]; team[to + 1].tot_dif = -9999; qsort(&(team[from]), to - from + 1, sizeof(team_t), cmp_tot_dif); for (i = from; i <= to + 1; i++) { if (temp == team[i].tot_dif) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].tot_dif; } /* Restore */ team[to + 1] = temp_team; for (i = 0; i < ties; i++) { #ifdef DEBUG printf("(2) > %d - %d\n", tie[i][0], tie[i][0] + tie[i][1] - 1); printf("(2)>> "); print(); #endif sort_tot_gol(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ int cmp_tot_win(const team_t *a, const team_t *b) { if (a->tot_win > b->tot_win) return -1; else if (a->tot_win == b->tot_win) return 0; return 1; } void sort_tot_win() { int ties = 0, temp = -9999, is_seq = 0; int tie[2][2]; int i; qsort(team, 4, sizeof(team_t), cmp_tot_win); /* 番兵が役に立つ... (i < 5) */ for (i = 0; i < 5; i++) { if (temp == team[i].tot_win) { if (!is_seq) { is_seq = 1; team[i].rank = i - 1; tie[ties][0] = i - 1; } else { team[i].rank = team[i - 1].rank; } } else { if (is_seq) { is_seq = 0; team[i].rank = i; tie[ties][1] = i - tie[ties][0]; ties++; } else { team[i].rank = i; } } temp = team[i].tot_win; } for (i = 0; i < ties; i++) { #ifdef DEBUG printf("(1) > %d - %d\n", tie[i][0], tie[i][0] + tie[i][1] - 1); printf("(1)>> "); print(); #endif sort_tot_dif(tie[i][0], tie[i][0] + tie[i][1] - 1); } } /* =========================================================================*/ /* =========================================================================*/ int is_target_rankin() { int i; for (i = 0; i < 4; i++) { if (team[i].numb == target) { if (team[i].rank == 0 || team[i].rank == 1) { return 1; } else { return 0; } } } return i / 0; } int target_rank() { int i; for (i = 0; i < 4; i++) { if (team[i].numb == target) { return (team[i].rank); } } return i / 0; } int howmany_tie_team_with_target() { int i; int howmany_by_rank[4] = {0, 0, 0, 0}; for (i = 0; i < 4; i++) { howmany_by_rank[team[i].rank]++; } for (i = 0; i < 4; i++) { if (team[i].numb == target) { return howmany_by_rank[team[i].rank]; } } return i / 0; } int main() { char str[120]; int N; int l; int a, b, c, d; double p; double add; int ties; int x = 0, y = 0; freopen("gucup.txt", "r", stdin); mkpt(); #ifdef DEBUG p = 0; for (l = 0; l < 9; l++) { printf("%f\n", pt[l]); p += pt[l]; } printf("%f\n", p); #endif gets(str); N = atoi(str); for (l = 0; l < N; l++) { input(); p = 0.0; for (a = 0; a <= 8; a++) { score[undec[0][0]][undec[0][1]] = a; for (b = 0; b <= 8; b++) { score[undec[1][0]][undec[1][1]] = b; for (c = 0; c <= 8; c++) { score[undec[2][0]][undec[2][1]] = c; for (d = 0; d <= 8; d++) { score[undec[3][0]][undec[3][1]] = d; mkteamdata(); is_recursed = 0; sort_tot_win(); switch (target_rank()) { case 0: add = pt[a] * pt[b] * pt[c] * pt[d]; ties = howmany_tie_team_with_target(); if (ties > 2) { add *= 2.0; add /= (double)ties; } p += add; break; case 1: p += pt[a] * pt[b] * pt[c] * pt[d] / (double)howmany_tie_team_with_target(); break; case 2: case 3: break; default: p /= 0.0; } } } } } printf("%.7f\n", p); } }