ChristmasSongTrauma
SRM 843 · 2023-01-03 · by misof
Problem Statement
Shopping before Christmas comes with many perils. One of them is the endless barrage of Christmas songs.
A few weeks ago Tommy needed to visit a shopping mall and spend visitTime consecutive seconds inside.
The shopping mall has a single tape with several distinct Christmas songs. They play the tape in an endless loop. The lengths of the songs on the tape (in seconds, in the order in which they are on the tape) are given in the
Depending on when Tommy enters the mall, he may hear a different number of songs. Hearing only a part of a song still counts as hearing the song.
We are only interested in distinct songs Tommy hears, so if he hears the same song multiple times, we only count it once.
Assume Tommy will enter the mall at some integer offset from the beginning of the tape, and that all offsets are equally likely. (The set of possible offsets includes zero = the start of the tape but excludes the end of the tape, as that is already also the beginning of its next loop.)
Tommy is lucky if the number of distinct songs he has to hear is minimal. (I.e., there is no other entrance time for which he would hear fewer distinct songs.)
Return the probability that Tommy will be lucky.
Notes
- Return values with an absolute difference at most 1e-9 will be accepted as correct.
- If a song stops playing at the same time Tommy enters the mall, or starts playing at the same time he leaves the mall, we do NOT count the song as heard by him.
Constraints
- playTime will have between 1 and 1000 elements, inclusive.
- Each element of playTime will be between 1 and 10^6, inclusive.
- visitTime will be between 1 and 10^9, inclusive.
{50, 100, 100, 100, 70, 90, 90}
300
Returns: 0.0016666666666666668
The loop of Christmas songs has 600 seconds. Tommy will be in the mall for 300 seconds. If he enters exactly 50 seconds after the start of the tape, he will only hear the three longest songs while at the mall. If he enters at any other time, he will hear at least four distinct songs.
{100, 100, 100, 100, 100, 100, 100, 100}
301
Returns: 1.0
All songs on this tape have the exact same length. Regardless of when Tommy enters he will hear four of the songs.
{312}
15241235
Returns: 1.0
Tommy will be in the mall for a very long time. Regardless of when he enters, he will be treated to an endless loop of Last Christmas and he will slowly lose his remaining shreds of sanity and his will to live. Regardless of when he enters, he will hear exactly one distinct song. Per our definition in the problem statement this means that for all possible offsets he will be lucky.
{50, 100, 100, 100, 70, 90, 90}
310
Returns: 0.41
The extra 10 seconds (in comparison to Example 0) now mean that Tommy will hear at least four distinct songs. His chance of hearing exactly four is somewhat less than 50 percent.
{50, 100, 100, 100, 70, 90, 90}
550
Returns: 0.0016666666666666668
Submissions are judged against all 142 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChristmasSongTrauma with a public method double fewest(vector<int> playTime, int visitTime) · 142 test cases · 2 s / 256 MB per case