HSHW - Highschool Homework


Hugo had quite a bad day today. His favourite high school subject, mathematics, was taught by his least liked substitute teacher - he always gave out an abnormally large amount of homework. Today was no different.

The teacher wrote N numbers on the board, and after a long thoughtful pause he told the class with a grin: "Well then, kids. For today's homework you will do this harmless exercise. As you can see, I've written quite a few numbers on the board, and your task is to find which two of them have the greatest product. Hm, now that I think about it, that would be too trivial. So you will also have to find which pair of numbers has the greatest quotient. Well, and now that we're at it, why don't you find the pair with the smallest quotient, too. And at that point you might as well find the pair with the smallest product. That should keep you busy for today's evening!".

Sigh.

How could someone even come up with such a boring, time-consuming and impractical task. If only there was someone who would help Hugo and do it for him.

Input

The first line of input contains the number 1 ≤ T ≤ 15: the number of test cases. T cases follow. The first line of each case contains the number 2 ≤ N ≤ 105: how many numbers the teacher wrote on the board. The second line contains N integers; their absolute value will be in the range [1, 106] (inclusive). In particular, notice that none of them are equal to zero. You may assume that in any input file, the sum of N across all test cases does not exceed 3*105.

Output

For each case, output five lines. The first one contains the number of the case x in the format "Case x:", starting at 1.

Then output four lines, each containing two integers from the input (let's call them x and y). They need to have the following properties (in this order):

x * y is the greatest possible
x * y is the lowest possible
x / y is the greatest possible
x / y is the lowest possible

If there are multiple pairs of integers which fulfil the criteria, output the one with the lowest x. x, y may be equal, but in that case their value has to appear at least twice in the input. All four lines are independent, that is the same integer from the input may be used across multiple lines. A number A is said to be greater than B if A > B and lower than B if A < B.

Example

Input:
1
3
5 -7 10

Output:
Case 1:
5 10
-7 10
10 5
10 -7

hide comments
David: 2022-01-13 22:00:24

This entire problem is a corner case! Need to shine a light in all the corners and identify the solution. Wrote just as much testing code, iterating over all possible values of x*y and x/y and computing the 4 values, and comparing to my problem solution. Take care, as the problem states, that if multiple pairs solve the problem, the pair with the lowest x is selected.

:D: 2019-07-15 23:03:09

Similarly to UNIHW, this problem seems easy, but requires careful coding to cover all possible cases. One general hint I would give here is to try brute force testing. Generate random array with positive and negative values and check all N*(N-1) ordered pairs for maxMul, minMul, maxDiv and minDiv. Use direct values comparison and integer arithmetic to avoid precision issues for division. Also induce cases with only positive and only negative values. Make sure to check small data like N=2 and N=3.

RE: Though there is a much shorter solution that doesn't handle corner cases :)

Last edit: 2019-07-20 17:08:02
akjol2049: 2018-11-29 10:34:43

Hi..Hodobox...i am getting WAs,, tried every goddamn corner cases..if you can tell me for which test my solution is getting WA..Thanks

RE: I see you got AC 20 minutes later. Hope you liked it :)

Last edit: 2018-11-30 19:14:10
vivek_dwivedi: 2018-06-20 11:34:53

@Hodobox please help me where i am getting WA ! Thanks in advance

RE: sometimes you use a number twice which only appears once on input
vivek_dwivedi :- thanks got it ! bdwy very gud question to work with corner cases.

Last edit: 2018-06-25 08:37:17
rishabhm123: 2017-05-29 19:41:56

@Hodobox..Can u please look into my code,,Why is it giving wrong answer.
As i have checked myself for all cases.
please

RE: you have AC for most cases, but have some WA even for n = 2; for example, you sometimes output the same number twice even if it does not appear twice in the input (also, although the judge is set to ignore extra whitespaces, you shouldn't output a blank line between test cases as in your last submit)

Last edit: 2017-05-29 22:08:04
akshayvenkat: 2017-05-03 15:22:34

@Hodobox, can you please check my submission? ID : 19338949

I have covered almost all of the cases , but still getting WA..

RE: I don't know if your solution passes otherwise, but you don't print Case #:\n! No space after ':'.
RE2: Even with it, you get WA for cases N=2

Last edit: 2017-05-03 17:41:47
akshayvenkat: 2017-05-03 14:33:01

Consider the input :
4
-90 -66 -31 -37

Both (-90)/(-31) and (-90)/(-37) are equal , with identical least X values(-90). What must be done in such a situation?

RE: (-90)/(-31) = 2.9032... (-90)/(-37) = 2.4324.... That is not equal!

RE(akshayvenkat): I'm sorry, i assumed we only had to consider the "quotient". Thank you for the swift reply :)

Last edit: 2017-05-03 14:38:29
eleonoragr: 2017-05-02 16:16:19

Last edit: 2017-05-03 04:19:58
hanstan: 2017-05-02 12:21:11

Can you give me any hint why my program is getting wrong answer?
Thank you.

RE: You have WA for very few cases - greatest x / y is wrong!

Last edit: 2017-05-03 09:36:17

Added by:Hodobox
Date:2017-04-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem