UNIHW - University Homework
Hugo had quite a bad day today. His favourite university subject, mathematical analysis, was taught by his least liked substitute teacher - he always gave out an abnormaly 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 smallest non-empty subset of them has the greatest product. That should keep you busy for today's evening!".
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.
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 1 ≤ N ≤ 105: how many numbers the teacher wrote on the board. The second line contains N integers; their absolute value will not exceed 109.
You may assume that in any input file, the sum of N across all test cases does not exceed 3*105.
For each test case, first print the string 'Case x: ', where x is the number of the test case, starting with 1. Then print a binary string (consistring of 0's and 1's) ; the ith character should be 1 if you decided to include the ith number from the input in the subset.
To make the output unambiguous, it should have the following properties:
- It should contain N characters, at least one of which has to be a 1.
- If we multiply the numbers from the input at whose indices this string has the character 1, the result will be the greatest possible.
- Out of all binary strings with the above properties, it should contain the minimum number of 1's.
- Out of all binary strings with the above properties, it should be lexicographically largest.
Reminder: To compare two valid strings lexicographically, find the first position from the left at which they differ. The one with a 1 at this position is lexicographically larger.
Input: 1 6 -2 -2 -3 4 5 1 Output: Case 1: 101110
The product of the subset this string represents is (-2) * (-3) * 4 * 5 = 120, which is the greatest possible. It uses the first -2 from the input, as using the second one would result in a lexicographically smaller string. It does not use the 1, as the product would remain the same but the number of 1's in the string would increase.
AC in 1 go!!!1
can you tell me why am i getting WA? I think it's something small