DMPG '19 G1 - Camera Calibration Challenge

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.5s
Memory limit: 128M

Authors:
Problem type

One of the recommendations made this year was for Kirito to make a pre-recorded opening speech for the DMPG that would be played at the satellite sites.

To achieve this, Kirito borrowed AvaLovelace's camera and digital art expertise. While fooling around with learning about the camera's features, he realized that he accidentally messed up the camera's exposure correction! Panicking, he recalls what she taught him about exposure:

A photo can be represented as a grid of N by M pixels, and the pixel in row i and column j has a brightness b_{i, j}, which can be any real number from 10^{-6} to 1 inclusive. If you average the brightnesses of all the pixels in a typical image, the result is called the proper exposure.

Most digital cameras have an exposure correction feature. By choosing a correction constant C and multiplying all the pixel brightnesses in an image by C, a darker or brighter image can be obtained. When applying a correction constant, if any pixel brightnesses become greater than 1, those values are "clipped" and reduced to 1.

Armed with this knowledge, Kirito knows that to re-calibrate the camera, he has to answer Q queries:

What is the correction constant necessary for the proper exposure of this image to be \varepsilon_i?

Since he would prefer not to work with floating-point numbers, for each query \varepsilon_i, he would like to know the smallest integer C' such that applying the correction constant C' \cdot 10^{-6} to the image results in a proper exposure greater than or equal to \varepsilon_i.

Constraints

1 \le N, M \le 1\,000
10^{-6} \le b_{i,j} \le 1.0
0 \le \varepsilon \le 1.0

Subtask 1 [10%]

Q = 1

Subtask 2 [90%]

1 \le Q \le 10^6

Input Specification

The first line of input will contain 2 space separated integers, N and M.
The next N lines will each contain M space-separated integers, the pixel brightnesses multiplied by 10^6.
This will be followed by a single integer, Q.
The next Q lines will each contain a single integer, \varepsilon_i multiplied by 10^6.

Output Specification

Q lines, where the ith line contains the smallest possible C' that will result in a proper exposure greater than or equal to \varepsilon_i.

Sample Input 1

2 3
360000 304000 120000
408000 312000 960000
1
480000

Sample Output 1

1250000

Sample Input 2

2 3
480000 580000 560000
380000 400000 480000
3
120000
480000
360000

Sample Output 2

250000
1000000
750000

Comments

There are no comments at the moment.