Facebook Hacker Cup 2014 Finals

Fortunate Wheels

Kit is competing on the latest popular gameshow, Fortunate Wheels. On this show, there is a secret word S (2 ≤ |S| ≤ 10⁵) consisting only of uppercase letters, known only to the host, and contestants can pay points to buy sequences of letters in hopes of matching part of S and earning more points! This show is clearly a scam, as the probability of earning more points than are spent is extremely low. Fortunately, Kit has come prepared – he knows the secret word! Even so, getting as many points as possible will not be easy.

There are N (1 ≤ N ≤ 20) basic deals which contestants can take. The i-th deal costs A_i points (1 ≤ A_i ≤ 10⁴), and allows any sequence of B_i letters (1 ≤ B_i < |S|) to be purchased. Furthermore, deals can be combined to purchase longer sequences! Combining a deal with cost C₁ and length L₁ with another deal (potentially the same one) with cost C₂ and length L₂ creates a new deal with cost C₁ + C₂ + W (0 ≤ W ≤ 10⁴) and length L₁ + L₂ (as long as L₁ + L₂ < |S|), which can in turn be used to create even bigger deals. For example, if W = 0, then a basic deal with cost and length equal to 1 could be combined with itself repeatedly to yield a new deal with both cost and length equal to any positive integer smaller than |S|.

Once Kit purchases a sequence of letters using one (potentially non-basic) deal, it will be matched against the secret word – twice! The host will spin the First Fortunate Wheel to select the starting index in S for the first matching, which is chosen uniformly at random such that the sequence will fit entirely within S. Then, the host will spin the Second Fortunate Wheel to select the starting index for the second matching, which is chosen uniformly at random such that the sequence will fit entirely within S and such that the value given by the First Fortunate Wheel will not be repeated. For example, if the sequence consists of a single letter, the First Fortunate Wheel might yield any of the indices in S with probability ¹/_|S| each, and then the Second Fortunate Wheel might yield any of the remaining indices with probability ¹/_{(|S| − 1)} each. On the other hand, if the sequence has length |S| − 1, then the first Wheel might yield either 0 or 1, and the second Wheel must yield the other. If, for both generated indices, the sequence miraculously happens to be equal to the substring of S of the same length starting at that index, then Kit will earn back Y×(|S| − |X − ℓ|)² + Z points (1 ≤ X < |S|, 0 ≤ Y, Z ≤ 10⁹), where ℓ is the length of the sequence. If even one letter is off in either matching, however, Kit will earn no points at all! What has the game show industry come to?

Kit is carefully considering his first turn of the game. He obviously wants to maximize the number of points he'll gain, but worries that choosing the very best move might be suspicious. As such, he'd like to find the expected point values of the M (1 ≤ M ≤ 20) best distinct moves before making his decision. Two moves are distinct if they involve purchasing different sequences of letters – the deal(s) used are ignored. Note that moves can have negative expected point values, due to the costs of deals.

Input

Line 1: 1 integer, T (1 ≤ T ≤ 150), the number of test cases

For each test case:
Line 1: 6 integers, N, M, W, X, Y, and Z
Line 2: 1 string, S
Next N lines: 2 integers, A_i and B_i, for i = 1..N

Output

For each test case, output M real numbers on one line (accurate to within 10⁻² in absolute or relative value), the M largest expected point values which can be earned, in descending order.

Sample Input

2
1 3 0 1 5 6
ZZ
2 1
3 4 1 4 3 2
FOXENINBOXEN
5 2
1000 11
2 2

Sample Output

24.00000 -2.00000 -2.00000
7.05556 3.49091 3.49091 3.49091

Explanation of Sample

In the first test case, Kit's best move is to use the basic deal, costing 2 points, to purchase the sequence of letters "Z". No matter what pair of indices the two Fortunate Wheels yield, this sequence will match and earn Kit 5×(2 − |1 − 1|)² + 6 = 26 points. Any other sequence shorter than S cannot match S at even a single index, so Kit's second- and third-best moves consist of using the basic deal to purchase any other single-letter sequence, and simply losing the 2 points.

In the second test case, Kit's best move consists of combining the third basic deal with itself to yield a deal with cost 5 and length 4, and then purchasing the sequence "OXEN". His three next-best moves, which are the only other moves which get him a positive expected point value, involve using the third basic deal to purchase the sequences "OX", "XE", and "EN".

All Submissions
Best Solutions

Point Value: 50
Time Limit: 60.00s
Memory Limit: 64M
Added: Jul 08, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)