Bitmap is a compression technology for redundant data compression. The ratio of Bitmap Compression is the size of compressed data divides by the size of original data. The following is an example, the left one is an original array, the middle one is a bitmap array and the right one is a compact table. The original array is original data.The bitmap array and the compact table is compressed data. The way of Bitmap Compression is showed in the figure. Each element of a bitmap array occupies one bit. The data type of elements in compact table is the same as in original array.
Assuming the type of elements in original array is char(which occupies 1Byte=8bit each), there are eighteen elements in total. So the size of original array is 1Byte * 18 = 18Byte. After compression the size of bitmap array and compact table are 18 bit and 6Byte. The compression ratio can be calculated as: (18bit + 6Byte) / (18Byte) = 11/24 = 0.458333. Some people may wonder that the Bitmap Compression is not always efficient in some situation. So does fengzlzl. Now given the original array, can you help fengzlzl to calculate compression ratio using Bitmap Compression?
The first line is an integer T which stands for the number of test cases. For each test case the first line is an integer N which stands for the number of elements in the original array, a blank space, and a string which stands for the data type of elements in original array. The string can only be "char" or "int". The size and range of these two types are the same as signed 8-bit integer or signed 32-bit integer in C/C++, Java. There are N space-seperated integers of the original array in the second line. The i-th integer stands for the element whose subscript is i-1.
For each test case output a float number stands for the compression radio, rounded to 6 digits after decimal point.
2 18 char 0 0 0 0 1 1 1 0 0 0 0 2 0 0 0 3 3 3 4 int -1 -1 -1 -1
Sichuan University Programming Contest 2011 Final