Rain vs City
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an n*m matrix A. A is the top-left cell, and A[n][m] is the bottom-right cell. You want to fill a matrix B[n][m] using the following pseudo code. All the entries of matrix B are zero initially.
randomInt(a, b) returns an uniform random integer between a and b (both inclusive). That is, all the b-a+1 integers have an equal probability of being returned.
For x = 1 to n: For y = 1 to m: I = randomInt(1, x) J = randomInt(1, y) K = randomInt(x, n) L = randomInt(y, m) Consider the rectangle formed by (I, J) as top-left and (K, L) as right-bottom cell. Add A[x][y] to every cell in the B matrix which is within this rectangle. This means B[p][q] += A[x][y] if I <= p <= K and J <= q <= L.
A city is constructed, which has n * m houses. The house located at (i, j) has height B[i][j] above sea level. After X amount of rainfall, all houses whose height is less than or equal to X are submerged in water.
Note than in the above construction, the heights of houses inside the city are not constant, but vary based on outcome of the previous algorithm.
You have to answer Q queries, where each query is defined by an integer k (0 < k < n * m). You have to find the smallest integer X, so that if there is X amount of rainfall, expected number of houses submerged in water are at least k.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three integers, n, m and Q.
The next n lines contain m space separated integers each, denoting the initial matrix A.
The next Q lines have one integer each, the query parameter k.
For each test case, for each query, output a single line containing the smallest value of integer X.
- 1 ≤ T ≤ 1000
- 1 ≤ n,m ≤ 20
- 1 ≤ A[i][j] ≤ 5
- 1 ≤ Q ≤ 400
- 0 < k < n*m
- The sum of n*m for all test cases in a single file does not exceed 500
Input: 1 1 2 1 2 3 1 Output: 3
These are the following possible values of B:
2 3 5 3 2 5 5 5All these four values of B appear with same probability, 1/4. The expected number of houses submerged when X = 3 is (2 * 1/4 + 1 * 1/4 + 1 * 1/4 + 0 * 1/4) = 1. if rainfall is less than 3, then the expected number of submerged houses is less than 1.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.