// Mugurel Ionut Andreica // Convert all the probabilities into integers with up to 4 digits and multiply them into a big number using a large base which is a power of 2 (in order to have quick division and modulo operations). #include #include #include #define DEBUG 0 #define NMAX 8010 #define BASE 262144 #define BASEMOD 262143 #define BASEBITS 18 typedef unsigned int BigNum[NMAX]; inline void Multiply(BigNum v, unsigned int x) { unsigned int i; if (x == 0) { memset(v, 0, (v[0] + 1) * sizeof(int)); v[0] = 1; return; } if (x == 1) return; v[1] *= x; for (i = 1; i <= v[0]; i++) { v[i + 1] *= x; if (v[i] >= BASE) { v[i + 1] += (v[i] >> BASEBITS); v[i] &= BASEMOD; } } for (i = v[0] + 1; v[i] > 0; i++) { if (v[i] >= BASE) { v[i + 1] += (v[i] >> BASEBITS); v[i] &= BASEMOD; } } v[0] = i - 1; } void Add(BigNum A, BigNum B) { unsigned int i, ndigits = A[0]; if (B[0] > ndigits) ndigits = B[0]; for (i = 1; i <= ndigits; i++) A[i] += B[i]; A[0] = ndigits; for (i = 1; i <= A[0]; i++) if (A[i] >= BASE) { A[i + 1] += (A[i] >> BASEBITS); A[i] &= BASEMOD; if (i == A[0]) A[0]++; } } void Subtract(BigNum A, BigNum B) { unsigned int i, j; for (i = 1; i <= A[0]; i++) { if (A[i] < B[i]) { j = i + 1; while (j <= A[0] && A[j] == 0) j++; A[j]--; j--; while (j > i) { A[j] = BASE - 1; j--; } A[i] += BASE; } A[i] -= B[i]; } while (A[0] > 1 && A[A[0]] == 0) A[0]--; } int Equal(BigNum A, BigNum B) { if (A[0] != B[0]) return 0; for (unsigned int i = 1; i <= A[0]; i++) if (A[i] != B[i]) return 0; return 1; } int LessThanOrEqual(BigNum A, BigNum B) { if (A[0] < B[0]) return 1; if (A[0] > B[0]) return 0; for (int i = A[0]; i >= 1; i--) { if (A[i] < B[i]) return 1; if (A[i] > B[i]) return 0; } return 1; } void PrintBigNum(BigNum A) { int i; fprintf(stderr, "%d", A[A[0]]); for (i = A[0] - 1; i >= 1; i--) fprintf(stderr, "%04d", A[i]); fprintf(stderr, "\n"); } char frac[10]; BigNum A, B, SUM; int N, M; int main() { int T, i, j, k, x, y; scanf("%d", &T); while (T--) { scanf("%d %d", &N, &M); memset(SUM, 0, sizeof(SUM)); SUM[0] = 1; for (i = 0; i < N; i++) { memset(B, 0, sizeof(B)); B[0] = B[1] = 1; for (j = 0; j < M; j++) { scanf("%d.%s", &x, frac); if (x == 0) { y = 0; sscanf(frac, "%d", &y); for (k = strlen(frac); k < 4; k++) y *= 10; x = x * 10000 + y; } else x = 10000; Multiply(B, x); } if (i == 0) memcpy(A, B, sizeof(BigNum)); Add(SUM, B); if (DEBUG) { fprintf(stderr, "i=%d: %d", i, B[0]); //PrintBigNum(B); fprintf(stderr, "\n"); } } if (DEBUG) { fprintf(stderr, "SUM= %d", SUM[0]); //PrintBigNum(SUM); fprintf(stderr, "\n"); } if (A[0] == 1 && A[1] == 0) printf("0.000000000\n"); else if (Equal(A, SUM)) printf("1.000000000\n"); else { printf("0."); // Find all the digits, one by one. for (int digit = 1; digit <= 9; digit++) { Multiply(A, 10); int li = 0, ls = 9, mid, ans = 0; while (li <= ls) { mid = (li + ls) >> 1; memcpy(B, SUM, sizeof(BigNum)); Multiply(B, mid); if (LessThanOrEqual(B, A)) { ans = mid; li = mid + 1; } else { ls = mid - 1; } } printf("%d", ans); if (ans > 0) { memcpy(B, SUM, sizeof(BigNum)); Multiply(B, ans); Subtract(A, B); } } printf("\n"); } } return 0; }