시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 29 | 11 | 9 | 39.130% |
Having solved the edit distance problem years ago, the head of Pry oil has a plan to streamline their formula library. A pry sequence, used to describe a Pry formula, is a sequence of lower-case letters (a through z). Such a sequence is a closely guarded secret and is managed by a computer program written by Pure Evil.
To record a new pry sequence, you have to start with an existing pry sequence and make edits. Pure Evil charges money for every alteration made. Each letter is priced differently:
val('a') == 1, val('b')==2, val('c')==3,..., val('z')==26.
Let A = a1a2...an (1 ≤ n ≤ 20,000) be an existing pry sequence, and B = b1b2...bm (1 ≤ m ≤ 20,000) be a new sequence to be recorded. You can:
For example: for a total cost of 3.21, you can turn 'ary' into 'tray' by (1) inserting 't' yielding 'tary' (cost: 1.2); (2) deleting 'a' yielding 'try' (cost: 1); and (3) inserting 'a' yielding 'tray' (cost: 1.01). However, you can do better. For a total cost of 3.11, you could instead (1) replace 'a' by 't' yielding 'try' (cost: 2.1); and (2) insert 'a' yielding 'tray' (cost: 1.01).
YOUR TASK: For a given pair of A and B, you will determine the cheapest cost to record B starting from A in Pure Evil's program. The head of Pry oil doesn't want to record any sequence that Pure Evil charges strictly more than K (0 ≤ K ≤ 100). For sequences that exceed the budget, you will output "TOSS" instead.
The first line contains the number of test cases 1 ≤ T ≤ 20. Following that, there will be T sets of test cases, each containing three lines formatted as follows:
You are to produce T lines. The i-th line contains the answer for i-th test case, reporting a single number that indicates the cost (with exactly 4 digits of accuracy) to make the pry sequence B from the given pry sequence A. If the cost exceeds the budget K, output the word “TOSS”. Note: Use printf(“%.4f”) available in both C/C++ and Java to correctly format the output.
3 4 ary tray 5 llllammpptp llllammpppt 3 bcabcabcabcabcabca abcbacabcabacbcabc
3.1100 2.1600 TOSS