DMPG '18 B4 - Shimnanigans (Hard Version)

View as PDF

Submit solution

Points: 6
Time limit: 1.0s
Memory limit: 64M

Problem type

Differences between this problem and the original problem will be bolded.

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 represents 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?

The original problem had weak test data, so this version will have stronger data. Users are encouraged to hack other submissions.

Constraints

1 \leq N, M \leq 10^3

30 \leq X \leq 100

Input Specification

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

The next line will each contain N space separated positive integers, representing the given numerators. The numerators will be at most 10^6.

The next line will each contain M space separated positive integers, representing the possible denominators. The denominators will be at most 10^6.

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

32

Sample Input 2

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

Sample Output 2

Shimnanigans have failed

Comments


  • 1
    Machine_A_Rajeunir  commented on Feb. 2, 2019, 10:04 p.m. edited

    Reply to DA_BIG_MO: The denominator is for all the numerators in list[0] .. list[N-1]


  • 0
    DA_BIG_MO  commented on Feb. 2, 2019, 9:56 p.m.

    for example two, why isn't 1/1 as the only fraction giving an average of 100% an acceptable solution