سلام
من اصلا نمی فهمم صورت سوال یک چه می گویید؟ شایید برای اینکه زبانم ضعیف هست.
حالا که زمان مسابقه تمام شده کسی می تواند برای من توضیح دهد؟
با تشکر
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
Problem
I have a really long password, and sometimes I make a mistake when I type it. Right now I've typed part of my password, but I might have made some mistakes. In particular, I might have pressed the wrong key while typing one or more of the previous characters. Given how likely I was to get each character right, what should I do?
I have three options:
Finish typing the password, then press "enter". I know I'll type the rest of the characters perfectly. If it turns out that one of the earlier characters was wrong, I'll have to retype the whole thing and hit "enter" again -- but I know I'll get it right the second time.
Hit "backspace" some number of times, deleting the last character(s) I typed, and then complete the password and press "enter" as in option 1. If one of the characters I didn't delete was wrong, I'll have to retype the whole thing and press "enter", knowing I'll get it right the second time.
Give up by pressing "enter", retyping the password from the start, and pressing "enter" again. I know I'll get it right this time.
I want to minimize the expected number of keystrokes needed. Each character in the password costs 1 keystroke; each "backspace" costs 1 keystroke; pressing "enter" to complete an attempt or to give up costs 1 keystroke.
Note: The "expected" number of keystrokes is the average number of keystrokes that would be needed if the same situation occurred a very large number of times. See the example below.
Example
Suppose my password is "guest" and I have already typed the first two characters, but I had a 40% chance of making a mistake when typing each of them. Then there are four cases:
I typed "gu" without error. This occurs with probability 0.6 * 0.6 = 0.36.
I typed the 'g' correctly but I made a mistake typing the 'u'. Then I have two letters typed still, but the second one is wrong: "gX". (Here, the 'X' character represents a mistyped letter.) This occurs with probability 0.6 * 0.4 = 0.24.
I typed the 'u' correctly but I made a mistake typing the 'g': "Xu". This occurs with probability 0.4 * 0.6 = 0.24.
I made a mistake typing both letters, so I have two incorrect letters: "XX". This occurs with probability 0.4 * 0.4 = 0.16.
I don't know how many mistakes I actually made, but for any strategy, I can calculate the expected number of keys required to use it. This is shown in the table below:
"gu" "gX" "Xu" "XX" Expected
Probability ۰/۳۶ ۰/۲۴ ۰/۲۴ ۰/۱۶ -
Keystrokes if I keep typing ۴ ۱۰ ۱۰ ۱۰ ۷/۸۴
Keystrokes if I press backspace once ۶ ۶ ۱۲ ۱۲ ۸/۴
Keystrokes if I press backspace twice ۸ ۸ ۸ ۸ ۸
Keystrokes if I press enter right away ۷ ۷ ۷ ۷ ۷
If I keep typing, then there is an 0.36 probability that I will need 4 keystrokes, and an 0.64 probability that I will need 10 keystrokes. If I repeated the trial many times, then I would use 4 keystrokes 36% of the time, and 10 keystrokes the remaining 64% of the time, so the average number of keystrokes needed would be 0.36 * 4 + 0.64 * 10 = 7.84. In this case however, it is better to just press enter right away, which requires 7 keystrokes.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers, A and B. A is the number of characters that I have already typed, and B is the total number of characters in my password.
This is followed by a line containing A real numbers: p1, p2, ..., pA. pi represents the probability that I correctly typed the ith letter in my password. These real numbers will consist of decimal digits and at most one decimal point. The decimal point will never be the first or the last character in a number.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the expected number of additional keystrokes I need, not counting the letters I have typed so far, and assuming I choose the optimal strategy. y must be correct to within an absolute or relative error of 10-6.
