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.

Time complexity: $$$O(1)$$$

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.

Time complexity: $$$O(N)$$$

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.

Time complexity: $$$O(HW)$$$

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.)

Time complexity: $$$O(\lceil R \rceil)$$$ or $$$O(\lceil R \rceil \log \lceil R \rceil)$$$

Construct the weighted directed graph and run Dijkstra's algorithm from each node. However we have to deal with the fact that the goal node is the same as the source node. There are several ways:

• Set the cost of the source node to $$$\infty$$$ and prepopulate the priority queue with the nodes directly reachable from the source
• Create a new fictional node $$$n+1$$$ to use as the goal node. Redirect all back-to-source edges there.
• First precalculate the cheapest edge from each node to the source node (or $$$\infty$$$ if there are none). Run Dijkstra as normal, then add the costs and find the minimum.

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.