EvilCakeCutter
TCC19 South America Prelims · 2019-06-10 · by erinn
Problem Statement
You and another baker are working on cutting a w x h sheet cake into pieces. Each piece must be a w1 x h1 rectangle with sides parallel to the sides of the cake. Note that the pieces cannot be rotated: the width of the piece must run in parallel to the width of the cake.
Your coworker does not like to work in any orderly fashion. He has decided to cut out the first piece completely at random. More precisely, he will choose the location of the top left corner of the cut uniformly at random from all possible locations such that the entire cut lies within the cake. (Note that the coordinates may be arbitrary real numbers, not just integers.)
Calculate the probability that after his cut you will still be able to cut out at least one more piece of the same size.
Constraints
- w1 will be between 1 and w, inclusive.
- h1 will be between 1 and h, inclusive.
- w will be between w1 and 1,000,000, inclusive.
- h will be between h1 and 1,000,000, inclusive.
3 2 1 1 Returns: 1.0
It's always possible to get a second piece.
2 2 1 1 Returns: 0.0
The only way a second piece can be cut, is if the first piece comes perfectly from a corner, or perfectly along the edge. Since the evil cut is chosen continuously, the probability of this is infinitesimally small.
8 5 3 2 Returns: 0.9333333333333333
Only if the first cut is right near the middle, leaving too small a width or height anywhere around it, can a second piece not be cut. In most cases getting a second piece is possible.
1000000 1000000 345678 456789 Returns: 0.9614101733636184
58 45 23 19 Returns: 0.8549450549450549
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EvilCakeCutter with a public method double successProbability(int w, int h, int w1, int h1) · 46 test cases · 2 s / 256 MB per case