DMPG '18 B4 - Shimnanigans

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

As Mr. Shim (your favourite math teacher) always says, you control the numerator and he controls the denominator. While you may control the numerator, Mr. Shim can manipulate the denominator as he pleases, and thus controls the value. There are N students in the class, and you will be given N numerators that represent the grade of each student. You will also be given M denominators, the denominators that Mr. Shim is considering using. It is your job to choose the optimal denominator for your class in order to obtain the class average of X.

There are however, a few concerning limitations! The most important one is that students are not allowed to have a grade over 100\%, meaning that the numerator can never be larger than the denominator. Additionally, you also cannot allow the class to fail (to have an average below 50\%). If no such denominators meet those limitations, then output Shimnanigans have failed. Which denominator gives the average closest to X?


1 \le N, M \le 10^3

30 \le X \le 100

Input Specification

The first line will contain space separated integers, N, M and X.

The next line will contain N space separated integers, representing the given numerators.

The next line will contain M space separated integers, representing the possible denominators.

Output Specification

Output the denominator that will place the average closest to X. If no denominators are valid, then output Shimnanigans have failed. If there are two denominators that yield equally close averages, output the larger one because you love your classmates.

Sample Input 1

3 3 100
23 31 27
27 35 32

Sample Output 1


Sample Input 2

10 1 87
7 2 3 4 3 5 11 1 2 8

Sample Output 2

Shimnanigans have failed


There are no comments at the moment.