Little Elephant and Blocks
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Elephant from Zoo of Lviv has n (0-based numeration) blocks consisted of 1x1x1 cubes in such way that the size of i-th block is 1x1xAi. Each of the blocks also has a color, which is a positive integer. The color of i-th block is Ci. There will be no more than two blocks of the same color.
Little Elephant wants to stack the blocks in the stack. In order to do so, he choose some random permutation P of integers from 0 to n-1, inclusive, and stacks all the blocks in order of P, i. e. at first he stacks P0-th block, then P1-th and so on.
After stacking Little Elephant has a sequence of size S consisted of cubes (0-based numeration) in order from the stack, where S = A0 + A1 + ... + An-1. Then he counts the number of such pairs of cubes with indices i and j that j - i = k and i-th cube has same color as j-th. Call this number as colorfulness of the corresponding permutation.
Help Little Elephant and for a given n, k and the description of blocks find the expected colorfulness, considering that permutation P is chosen randomly.
First line of the input contains single integer T - the number of test cases. Then T test cases follow. First line of each test case contains pair of integers n and k. Next n lines of each test case contain pairs of integers Ai and Ci.
In T lines print T numbers - the answers for the corresponding test cases. Your answer will considered correct if it has at most 10-6 absolute or relative error.
1 ≤ T ≤ 10
1 ≤ n ≤ 20
1 ≤ k ≤ 200
1 ≤ Ai ≤ 10
1 ≤ Ci ≤ n
There will be no three or more blocks of the same color in a single test case.
Input: 1 7 5 3 1 2 2 2 1 4 3 1 2 1 3 4 4 Output: 0.9095238
|Tags||combinatorics, dynamic-programming, june14, medium, witua|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.