Woburn Challenge 2016-17 Round 1 - Senior Division

Problem 4: TP

You and your friends have had enough of this Halloween nonsense. You nabbed your fair share of candy in the past, sure, but you wouldn't be caught dead parading around in a costume now that you're in high school. That doesn't mean this dumb excuse for a holiday has to go to waste, though... No way. It's time to have some real fun.

There are N (2 ≤ N ≤ 10⁷) nice-looking houses on your street, but they won't be looking nice for long. Having borrowed your family car for the night, you'll be taking a joy ride down the street with your friends and some bathroom supplies in tow. Your plan is to take M (1 ≤ M ≤ 2000) passes along the street, and on each pass, you'll choose a random pair of distinct houses (chosen uniformly at random from all possible pairs) to be your targets. Then, those two houses will each receive a little punishment... Bam! Toilet paper to the face!

Once you've TP-ed a house in this fashion, it will be thoroughly covered in the stuff. It may get chosen as a target again on future passes, but applying toilet paper multiple times will have no additional effect on it.

This is sure to be a sweet night, but now you're wondering just how much carnage you and your friends will inflict on your lame neighbourhood. What's the expected number of different houses which will have been TP-ed at least once by the end of Halloween?

In test cases worth 4/35 of the points, N ≤ 5 and M ≤ 5.
In test cases worth another 5/35 of the points, N ≤ 10 and M ≤ 10.
In test cases worth another 18/35 of the points, N ≤ 1000 and M ≤ 1000.

Input Format

The first and only line of input consists of two space-separated integers N and M.

Output Format

Output one line consisting of a single real number – the expected number of houses which will be covered in toilet paper after all M passes, with at most 10⁻⁵ absolute or relative error.

Sample Input

3 2

Sample Output

2.666667

Sample Explanation

There are 3 possible pairs of distinct houses – 1&2, 1&3, and 2&3. Therefore, there are 9 equally-likely pairs of pairs of houses which will be TP-ed on the two passes. 3 of these result in only 2 distinct houses being covered in toilet paper (for example, 1&2 being targeted on both passes). The other 6 of them result in all 3 houses being covered. Therefore, the expected number of houses which will be covered in toilet paper is (3×2 + 6×3) / 9 = 8 / 3.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Oct 16, 2016
Author: SourSpinach

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

Comments (Search)