DMPG '18 B4 - Shimnanigans (Hard Version) - Olympiads Online Judge

DMPG '18 B4 - Shimnanigans (Hard Version)

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 0.6s

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$ $N$ students in the class, and you will be given $N$ $N$ numerators that represent the grade of each student. You will also be given $M$ $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$ $X$ .

There are however, a few concerning limitations! The most important one is that students are not allowed to have a grade over $100\%$ $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\%$ $50 %$ ). If no such denominators meet those limitations, then output Shimnanigans have failed. Which denominator gives the average closest to $X$ $X$ ?

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

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

Constraints

$1 \le N, M \le 10^3$ $1 \leq N, M \leq 10^{3}$

$30 \le X \le 100$ $30 \leq X \leq 100$

Input Specification

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

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

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

Output Specification

Output the denominator that will place the average closest to $X$ $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

Copy

3 3 100
23 31 27
27 35 32

Sample Output 1

Copy

Sample Input 2

Copy

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

Sample Output 2

Copy

Shimnanigans have failed

Comments

0

Machine_A_Rajeunir commented on Feb. 3, 2019, 3:04 a.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. 3, 2019, 2:56 a.m.

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

0

codeHH698 commented on Aug. 31, 2021, 8:32 p.m.

you need to get 87 not 100