| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13020 | Happy B to As with Weeheehea |
|
| 13098 | String Zip |
|
Description
Let's call a grid 8-puzzle board if the gridsize is 3 x 3 and there is exactly one cell is 'x' and others are '1' or '0'.
In one operation, you can exchange the 'x' cell of a 8-puzzle board with any cell which is adjacent to the 'x' cell. The cell (i, j) is adjacent to the cell (i-1, j), (i, j-1), (i, j+1) and (i+1, j) (if not out of bounds).
Now you are given N + 1 8-puzzle boards A1, A2, ..., AN and B. You need to answer how many 8-puzzle boards of A1, A2, ..., AN could be made into B in at most K operations.
Sample Explanation
Here are the N + 1 8-puzzle boards A1, A2, ..., AN and B of sample, where N = 4, K = 2.
0 x 0 0 0 0 0 0 0 0 0 1 0 x 0
1 0 1 1 x 1 0 1 1 1 0 x 1 0 1
0 0 1 0 0 1 x 0 1 0 0 1 0 0 1
A1 A2 A3 A4 B
A1, A2 and A4 could be made into B in K operations. The following show some feasible way to make them into B.
A way to make A1 into B in K operations:
0 x 0
1 0 1
0 0 1
A1 is as same as B in the beginning
A way to make A2 into B in K operations:
0 0 0 0 x 0
1 x 1 ========> 1 0 1
0 0 1 0 0 1
exchange (1,2)
A way to make A4 into B in K operations:
0 0 1 0 0 x 0 x 0
1 0 x ========> 1 0 1 ========> 1 0 1
0 0 1 0 0 1 0 0 1
exchange (1,3) exchange (1,2)
Input
The first line contains two integers N and K – the number of 8-puzzle boards in A and the maximum number of operations you can execute for each 8-puzzle board.
Then you are given A1, A2, ..., AN and B in the order. All of them are in 3 lines of 3 characters. Please refer to Sample Input.
It's guaranteed that:
- For testcase 1~6: 1 ≤ N ≤ 10, 0 ≤ K ≤ 7
- For testcase 7: 1 ≤ N ≤ 105, 0 ≤ K ≤ 7
- For testcase 8: 1 ≤ N ≤ 105, 0 ≤ K ≤ 10
To pass testcase 7 and 8, note the efficiency of your strategy(code). It may be a little hard, so maybe you can try to solve other problems first after you pass first six testcases.
Output
Output how many 8-puzzle boards of A1, A2, ..., AN could be made into B in K operations and then print a newline('\n').
Sample Input Download
Sample Output Download
Tags
Discuss
Description
ZIP is an archive file format that supports lossless data compression. There are many way to zip compress data nowadays, such as RLE, LZW,Huffman Coding ans so on. Today your friend think out a method similiar as RLE(run length encoding) to compress data.
The zip way purpose by your friend:
Given the sequence contain only English letter or digit, the runs of data(sequences in which the same data value occurs in many consecutive data elements) will be store as a single data value and count, rather than as the original run.
Take squence aaabbb444 for example, aaabbb444 can be encoded to 3a3b3'4'
When there are less than three consecutive "letters", you don't need to compress it.
For example, aabbbdcccc can be encoded to aa3bd4c.
For those non-consecutive "digits", simply store the digit, you don't need to store the count.
For example, aabbb1ccc2dd33dd can be encoded to aa3b'1'3c'2'dd2'3'dd
Besides encoding, your friend is also interested in the compress rate of the result, which is defined by
Compress Rate = (length of the encoded string)/(length of the original string).
He ask you to help him implement the zip algoithm program and analysis the compress rate of the method. As the best friend of you, you decided to try your best to finish the program.
Input
Given a sequence contain only English letter or digit.
(2 <= the length of the sequence <= 1000)
Output
Print out the zip string and the compression rate, both followed by a newline character.
If the compression rate is less than 1.0 then print out "Compress rate: X.XXX" with the result (round to the third digit after the decimal point), otherwise print out "The string can't zip".
You can use printf("Compress rate: %.3f\n", rate) for printing the result.