| Submit | All submissions | Best solutions | Back to list |
VISIBLEBOX - Decreasing Number of Visible Box |
Shadowman loves to collect box but his roommates woogieman and itman don't like box and so shadowman wants to hide boxes as many as possible. A box can be kept hidden inside of another box if and only if the box in which it will be held is empty and the size of the box is at least twice as large as the size of the box.
Print the minimum number of box that can be shown.
Input
The input set starts with single line integer T (1<=T<=50) the number of test cases. Then following T cases starts with an integer N (1<=N<=100000) denoting the number of box. The next line contains N space separated positive integer. i-th of them contains a numbers Ai(1<=Ai<=100000) size of the i-th box.
Output
Output the the case number and the minimum number of box that can be shown.
Example
Input: 2 4 1 2 4 8 4 1 3 4 5 Output: Case 1: 1 Case 2: 3
| Added by: | imranziad |
| Date: | 2015-11-25 |
| Time limit: | 0.5s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
| Resource: | AIUB CS Fest 2015 (Mokaddesh Rashid Shovon) |
hide comments
|
2018-01-09 11:57:35
Thank You @shubhamGupta for the test cases |
|
|
2016-06-12 16:22:02 Admin Deepak Baghel
Easy O(max(A(i))) solution :) |
|
|
2016-01-31 08:46:17 Baojun Wang
time limit too strict except c/c++ Last edit: 2016-01-31 08:46:48 |
|
|
2015-12-23 12:54:25 manitejavarma
Is the given input sorted or not? |
|
|
2015-12-02 05:38:45 Shubham Gupta
Few points to be noted: The input array given is not in sorted order. Do maintain a tag/index/map for a counter of each element. Sample: Input: 2 4 1 1 1 4 8 1 1 1 1 3 4 4 6 Output: 3 4 |
RSS