I don't know why there were so many submitted O(n^2) DP solutions. Here is a simple formula for this problem:
answer = n - (yes + yes*(yes-1) + no*(no-1))/n, where yes = s-2*n and no = n-yes are the total numbers of occurrences of corresponding strings in answer.txt.
You can easily derive this if you try to think of probability of the same verdict for two arbitrary consecutive tests.

# Alternative Solution

Valentine is a veteran of programming contests and he's been working in the program committee for many years. He is very busy this week: the bike is under repair, some problems with Indian colleagues have to be solved, and five student groups are to be examined in philosophical problems of mathematics at the university. To crown it all, the new chairman of the program committee asked Valentine to write an alternative solution for one of the problems of the forthcoming contest.

Valentine was so busy that he had no time to read the problem statement. He only glanced at the output format and understood that it was required to output either `YES`, or `NO`.

Fortunately, Valentine was well acquainted with the testing system used in the contest. The system successively runs a solution on all tests of a problem, and for each test the checking process goes as follows. The input is copied to the file input.txt. Then the solution is launched. It reads the input from the file input.txt and writes the result to the file output.txt. When it finishes, the correct answer is copied to the file answer.txt. If the contents of the files answer.txt and output.txt match, the test is assumed to be passed; otherwise, the test is not passed.

Valentine decided to write a program that would operate as follows. If the folder containing the program doesn't contain the file answer.txt (i.e. the program is run on the first test), then the program outputs `YES`. Otherwise, the program outputs the contents of the file answer.txt.

Valentine plans to tell the chairman of the program committee that there is a nontrivial mistake in his program, and this mistake, fortunately, shows itself when the program is run on the excellent hard tests prepared by the author of the problem. However, first Valentine has to estimate the number of tests that his solution won't pass. Valentine doesn't have access to the tests, but he knows the number of tests and the total size of the files with answers. He also knows that the size of the file with the answer `YES` is 3 bytes, the size of the file with the answer `NO` is $2$ bytes, and all the variants of the order of tests are equally probable. Help Valentine to calculate the average number of tests that his solution won't pass.

## Input

The only line contains two integers $n$ and $s$ ($1 \le n \le 5000$; $2n \le s \le 3n$) which are the number of tests and the total size of the files with answers, respectively. The numbers are separated with a space.

## Output

Output the average number of tests that Valentine's solution won't pass, accurate to $10^{-5}$.

## Sample

### input

```
3 7
```

### output

```
2.0000000
```

Let a=s-2n,b=3n-s.
Then the answer is (2ab+b)/n.
Try it, you won't regret it!

answer=(2s-4n+1)(3n-s)/n

a is the number of NO ; b is the number of YES
ans=a/n+(n-1)*(a/n)*(b/(n-1))+(n-1)*(b/n)*(a/(n-1))
   =a/n+2ab/n
   =a*(1+2b)/n

Some tests?

i've been thinking at this problem for 2 weeks. can somebody give me a hint ?

always wa at test 11,why?

The "YES" come from two ways:1) when there is not have answer.txt;2) when answer.txt contain it.but i can't figure out this related to pass test! pass test should be the output.txt's content is same to  answer.txt. how to explain the hint's explanation?

No matter when I used double or long double, my code still got TLE.

Opt[Now][j][0] = Opt[Pre][j][0] + Opt[Pre][j][1] + Opt[Pre][j][3];
Opt[Now][j][1] = Opt[Pre][j - 1][0] + Opt[Pre][j - 1][2] + Opt[Pre][j - 1][1];
Opt[Now][j][2] = Opt[Pre][j][2] + Opt[Pre][j][3];
Opt[Now][j][3] = Opt[Pre][j - 1][2] + Opt[Pre][j - 1][3];

I had to write a Pascal code using extended and got AC.
Could anyone tell me how to AC in C++?

During 3 days I couldn’t find appropriate way
to work with big binomials having lost of order
or overflow. Simple and clever routine was found and
gave satisfaction.