UNIHW - University Homework

no tags 

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 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 smallest non-empty subset of them has the greatest 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 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.

Output

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 (consisting 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:

  1. It should contain N characters, at least one of which has to be a 1.
  2. If we multiply the numbers from the input at whose indices this string has the character 1, the result will be the greatest possible.
  3. Out of all binary strings with the above properties, it should contain the minimum number of 1's.
  4. 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.

Example

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.


hide comments
David: 2022-01-14 20:33:58

This problem, along with Highschool Homework, are exclusively corner case problems.
Ability to obtain an AC will depend on the quality of the code used to generate test cases.

atiqurrahman: 2019-09-01 16:55:44

the corner cases!

:D: 2019-07-13 00:14:32

Well, it's basically "Corner case, the problem" done really well. Great idea for a SPOJ task, thanks Hodobox.

Last edit: 2019-07-13 02:11:41
nadstratosfer: 2018-04-23 03:12:13

AC in 1 go!!!1

... after 2.5 hrs debugging and corner case handling. Hodobox you sadist!

ks1999: 2017-05-03 21:02:57

Ok thanks.

ks1999: 2017-05-03 11:44:30

can you tell me why am i getting WA? I think it's something small

RE: you are right - which means you can surely find it yourself :)

Last edit: 2017-05-03 14:39:31

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