Snack Party

Eating probabilities and prefix sums

Let $X_i$ indicate whether snack $i$ is eaten, and let $e_i$ be its eating probability. By linearity of expectation, the answer for $[l,r]$ is

$$\mathbb{E}\left[\sum_{i=l}^{r}X_i\right]=\sum_{i=l}^{r}\mathbb{E}[X_i]=\sum_{i=l}^{r}e_i.$$

The eating events need not be independent. Every question refers to the same entire process, so compute the $e_i$ values only once from the beginning.

DP on the fullness distribution

Let $dp[s]$ be the probability that fullness is $s$ immediately before the current snack. Initially $dp[0]=1$ and all other entries are zero. For snack $i$, define

$$q_s=\max(0,p_i-0.05s).$$

Then

$$e_i=\sum_{s=0}^{20}dp[s]q_s.$$

Initialize a fresh distribution $ndp$ to zero and, for every $s$, add

$$ndp[\min(20,s+1)]\mathrel{+}=dp[s]q_s,$$ $$ndp[\max(0,s-1)]\mathrel{+}=dp[s](1-q_s).$$

Replace $dp$ by $ndp$. Do not update in place: that would reuse an outcome of the current snack as an input to the same step.

Store $F_0=0$ and $F_i=F_{i-1}+e_i$. Each answer is . Do not reset the distribution at the left endpoint of a question. Keeping only the mean fullness is also insufficient in general: truncation of eating probabilities at zero and the boundary at fullness zero make future behavior depend on the distribution, not just its mean.

Correctness and complexity

Assume $dp$ is the correct current distribution. The two transitions multiply each state probability by the given conditional probabilities and partition all outcomes into eating and not eating. They send each outcome to precisely its next fullness. Thus $ndp$ is the correct next distribution, and the law of total probability gives the correct $e_i$. The initial distribution is correct, so induction proves all computed probabilities correct. Linearity of expectation and prefix sums then give every requested answer.

There are 21 fullness states. The complexity is $O(21N+Q)$ time and $O(N)$ space including prefix sums. Read and answer questions one by one without storing them.

Small inputs and numerical handling

Subtask 1 has $N\leq8$. Enumerate every sequence of eating/skipping decisions. With $c_i=100p_i$, the eating numerator at a step is , and the skipping numerator is its complement to 100. All outcomes have common denominator . Multiply their step numerators and add each leaf weight to the numerators for the snacks eaten in that outcome. This takes time and space.

Here the denominator is at most $10^{16}$ and any prefix expectation numerator is at most $8\cdot10^{16}$, so signed 64-bit arithmetic is exact. For the full constraints, do not construct the enormous exact denominator. Use sufficiently precise floating-point values for the distribution and prefix sums. The main solution parses $p_i$ as integer , computes in long double, and prints 15 digits after the decimal point. Every expected count lies between zero and the interval length.

The checker requires finite numbers and tests $|a-b|\leq10^{-6}\max(1,|b|)$ for contestant value $a$ and reference value . This is equivalent to the specified absolute-or-relative error criterion.

Independent verification

A separate implementation updates the cumulative distribution $C_j=P(S\leq j)$ instead of state probabilities. For $j<20$,

$$C'_j=C_j-P(S=j)q_j+P(S=j+1)(1-q_{j+1}),\qquad C'_{20}=1.$$

Also $q_{20}=0$. The usual change of minus one is blocked only when skipping at fullness zero, so

$$e_i=\frac{\mathbb{E}[S']-\mathbb{E}[S]+1-P(S=0)(1-p_i)}{2}.$$

Compute the mean by $\mathbb{E}[S]=\sum_{j=0}^{19}(1-C_j)$. This cumulative-distribution and mean-drift implementation was compared on all data, while small inputs were also checked by exact integer-numerator enumeration.

Solution written by GPT6