The ball is invisible when it's between $$$V \cdot T$$$ and $$$V \cdot S$$$ meters away, inclusive. Thus the answer is Yes if $$$D < V \cdot T$$$ or $$$D > V \cdot S$$$, and No otherwise.

Either use a dynamic array (vector in C++ / ArrayList in Java/Kotlin) to store the values $$$A_i \neq X$$$, or construct the output string directly. If using the latter method in Java/Kotlin, one should use the StringBuilder class to avoid wasting time copying the string in $$$O(n^2)$$$; this is not a problem in C++ as strings are mutable there.

Simulate a "wall-following" algorithm. Specifically, let . represent empty space, and # represent walls. Find the first # character in reading order. Stand to its north, facing east, with your right hand on the "wall". Then walk forwards. If your hand runs out of wall, turn right, if you run into a wall, turn left, incrementing the answer each time you change direction. Stop when you return to your starting position.

Working with double floating points in this problem may cause precision issues. It's best to multiply the input by $$$10^4$$$ and convert to signed 64-bit integers right away (note that if you're reading the input as a floating point, you need to round before converting). Now the problem becomes the number of points in the circle where $$$X$$$ and $$$Y$$$ are both divisible by $$$10^4$$$.

Iterate through the multiples of $$$10^4$$$ between $$$Y - R$$$ and $$$Y + R$$$ inclusive; let the current value be $$$y$$$.

Now you want to find the minimum and maximum $$$x$$$ that remains in the circle. Either binary search for them, or use sqrt to solve $$$(x - X)^2 + (y - Y)^2 \leq R^2$$$; however since sqrt uses floating points, brute force its neighborhood to avoid precision issues. Then add $$$\displaystyle\left\lfloor\frac {max} {10^4} \right\rfloor - \left\lceil\frac {min} {10^4} \right\rceil + 1$$$ to the answer.

One must also be careful with the divisions, as the behavior of the / operator may differ depending on the sign of the dividend. (In C++ and Java/Kotlin, it truncates, i.e., rounds toward zero, instead of finding the floor consistently.)

Reframe the problem as: for each tidy square, how many configurations will light it? This sum is equal to the sum the problem asks for.

Let $$$p_{i, j}$$$ denote the number of positions a lamp can be placed to light square $$$(i, j)$$$. This can be precalculated in $$$O(HW)$$$ by two-pointer technique (whenever you encounter a wall or the end of a line, add the run-length to the tidy squares. This can be done both horizontally and vertically, but remember to subtract $$$1$$$ from the end as the square $$$(i, j)$$$ itself will be counted twice)

The number of configurations that light a tidy square $$$(i, j)$$$ is equal to the total number of configurations minus the configurations that don't light the square (i.e. all the places that could light this square are left empty), thus the sum for that square is $$$2^K - 2^{K - p_{i, j}}$$$.

Thanks to Everule for help with this problem.

Let's denote the random variates with $$$X_i$$$ (capital X) to avoid confusion with the parametric variable $$$x$$$ in the following notations.

Let $$$F(x) := \Pr[\max X \leq x]$$$, the cumulative distribution function (CDF) of the maximum variate. There is a formula for deriving the expected value from the CDF of a random variate:

The latter integral can be ignored as $$$F(x) = 0$$$ for all $$$x \leq 0$$$. We can also adjust the upper bound of the left integral to $$$\max R$$$ as $$$F(x) = 1$$$ when $$$x \geq \max R$$$. Thus we may simplify:

Now let's figure out the behavior of $$$F(x)$$$. We may note that it's the product of the CDFs of all the individual random variates:

Let $$$f_i(x) := \Pr[X_i \leq x]$$$. Let's decompose $$$f_i(x)$$$, the CDF for a single variate:

Note that the middle expression is a degree-$$$1$$$ polynomial. To analyze the behavior of $$$F(x)$$$ we can imagine a sweep line on decreasing $$$x$$$. When $$$x$$$ touches the $$$R_i$$$ of one of the given intervals, its corresponding $$$f_i(x)$$$ "switches on" and contributes its middle expression to the product. Then as soon as $$$x$$$ touches $$$\max L$$$ one of the CDFs goes to $$$0$$$, which sets the product to $$$0$$$ for good. (This matches intuition, as the maximum variate could never be less than $$$\max L$$$). From this we can conclude that $$$F(x)$$$ is a piecewise function, with each piece being describable by a polynomial. We can integrate each piece individually, and their sum would be the integral of $$$F(x)$$$.

What does this mean in terms of implementation? We could at first set variable $$$E := \max R$$$, and sort all intervals in non-increasing (descending) order of $$$R_i$$$ (henceforth we assume $$$R_i \geq R_{i+1}$$$ for all $$$1 \leq i \leq N-1$$$). Let $$$m$$$ denote the number of intervals where $$$R_i > \max L$$$. Let $$$S_{1..m} := R_{1..m}$$$, and $$$S_{m+1} := \max L$$$, which together denote the change-points of $$$F(x)$$$.

Now let $$$p_0(x)$$$ be the polynomial $$$1$$$ (storing all polynomials as arrays of coefficients). As you iterate $$$i$$$ over $$$[1, m]$$$, construct the new polynomial:

Then integrate this polynomial over $$$[S_{i+1}, S_{i}]$$$ (the formula being derivable from the power rule for integrating polynomials):

Subtract each integral from $$$E$$$ and we have our desired expected value. Don't forget to multiply by the required scaling factor $$$(N+1)! \cdot \prod_{i=1}^N (R_i - L_i)$$$ before outputting.

This works in $$$\tilde O(N^2)$$$ as the polynomial increases in length by $$$1$$$ each iteration, taking about $$$\tilde O(n)$$$ to multiply and to integrate. The tildes (~) over the O's indicate hidden $$$\log$$$ factors from modular inverses and exponentiation. It can also be optimized to strict $$$O(N^2)$$$ using the multiple inverse trick and by accumulating the powers instead of exponentiating each time.