एसएचएडी 2020 में परीक्षा के पहले भाग का पूर्ण विश्लेषण

, — . , . , , ( ).

, , , , $$$f(x) = x^4 - (a + 1)x^3 + (a - 2)x^2 + 2ax$. , : $$$-1, 0, 2, a$. , $$$f(x) = (x + 1)x(x - 2)(x - a)$.

, $$$+ \to - \to + \to - \to +$, . , $$$a = -1, 0, 2$. , .

, $$$a = 1$. $$$\sqrt{\frac{1}{x}} \to 0$, :

$$

$$\cos{\sqrt{\frac{1}{x}}} = 1 - \frac{1}{2!x} + \frac{1}{4!x^2} - \frac{1}{6!x^3} + \ldots$$

. , , , , . , . :

$$

$$1 - \frac{1}{2x} < \cos{\sqrt{\frac{1}{x}}} < 1 - \frac{1}{2x} + \frac{1}{24x^2}$$

$$$x \to +\infty$, $$$x$ , . , $$$e^{-1/2}$. , :

$$

$$\lim_{x \to +\infty} \left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)^x = \exp\left(\lim_{x \to +\infty} x \ln\left( 1 - \frac{1}{2x} + \frac{1}{24x^2} \right)\right) =$$

$$

$$= \exp\left(\lim_{x \to +0} \frac{\ln\left( 1 - \frac{x}{2} + \frac{x^2}{24} \right)}{x}\right)$$

, . :

$$

$$\lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^x = e^{-1/2} \Rightarrow \lim_{x \to +\infty} \left(\cos{\sqrt{\frac{1}{x}}}\right)^{x/a} = e^{-1/2a}$$

$$$a = \frac{1}{2}$.

: , , .

, :

$$

$$x_k+1 = x_k - \lambda \triangledown f(x_k)$$

.

— , .

$$

$$\triangledown f(x_k) = 4x_k^3$$

$$$x_0$ , $$$x_1$:

$$

$$x_1 = x_0 - \lambda 4x_0^3 = 1 - 4\lambda$$

, $$$x_1=-1$ , $$$x_0$, . , , «» - $$$1$ $$$-1$ . , , $$$x_1=-1 \Leftrightarrow \lambda=0.5$ ( $$$0$). , $$$\lambda$ .

, . $$$|x_{n+1}| \leq |x_n||1-4\lambda|$ . , $$$0.5 > \lambda > 0 \Rightarrow |1 - 4\lambda| < 1$

:$$$|x_1| = |1 - 4\lambda| \leq 1 |1 - 4\lambda| = x_0 |1-4\lambda|$

. $$$|x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$. $$$x_n < 1 \Rightarrow x_n^2 < 1$. $$$|x_{n+1}| \leq |x_n||1-4\lambda|$. .

, , $$$|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n$. , $$$|1-4\lambda| < 1$, $$$|x_n|$ . .

, $$$v \neq 0$ $$$A$, $$$\exists \lambda$: $$$Av = \lambda v$. :

$$

$$\begin{pmatrix} a & 1 & -1 \\ 1 & 2 & -1\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 3 - a \\ a \\ \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 1 \\ a \\ \end{pmatrix}$$

. $$$\lambda = 1$, — $$$a = 2$, , . , $$$a = 2$.

:

$$

$$\det(a) = \begin{vmatrix} a & -7 & -3 \\ 6 & -10 & -a^2 \\ 0 & a & 9 \\ \end{vmatrix} = a \begin{vmatrix} -10 & -a^2 \\ a & 9 \\ \end{vmatrix} - 6 \begin{vmatrix} -7& -3 \\ a & 9 \\ \end{vmatrix} = a^4 - 108a + 376$$

$$

$$\det'(a) = 4a^3 - 108 = 0 \Leftrightarrow a = 3$$

, , , , , $$$\det(a)$, $$$\det(a) \geq \det(3) > 0$ $$$a = 3$. , $$$\det(A^{-1}) = \det(A)^{-1}$, , $$$a = 3$.

$$$A = (x, y, z)$ , $$$B$, , $$$B$. , , $$$\alpha$ $$$\overline{n}_1(2, -2, 1)$. :

$$

$$\begin{cases} x = 2t_1 + 1\\ y = -2t_1 + 2\\ z = t_1 - 3\\ \end{cases}$$

, $$$A$ , $$$C$ $$$\beta$. : $$$\overline{n}_2(-1, 2, 3)$, :

$$

$$\begin{cases} x = -t_2 + 2\\ y = -2t_2 + 2\\ z = 3t_2 + 1\\ \end{cases}$$

. $$$t_1$ $$$t_2$, :

$$

$$\begin{cases} 2t_1 + 1 = -t_2 + 2\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} 3 = t_2 + 4\\ -2t_1 + 2 = 2t_2 + 2\\ \end{cases} \Leftrightarrow \begin{cases} t_2 = -1\\ t_1 = 1\\ \end{cases}$$

, , $$$A(3, 0, -2)$, .

$$$\xi$, $$$\Omega$ $$$\xi(\Omega)$. :

$$

$$E(\xi) = \sum_{k \in \xi(\Omega)} k \Pr[\xi = k] = 2$$

$$$A_k$ — , $$$K$, $$$\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$. $$$|\Omega|$, :

$$ $$\sum_{k \in \xi(\Omega)} k |A_k|= 2 |\Omega|$$

$$$|\Omega|$. -, . -, , . ,

$$ $$|\Omega| = n + 1 + \frac{n(n + 1)}{2}$$

.

. , 0 $$$n$. $$$k$? $$$n - k + 1$: — $$$(0, k), (1, k + 1), \ldots, (n - k, n)$. :

$$ $$\sum_{k \in \xi(\Omega)} k |A_k| = \sum_{k = 0}^n k(n - k + 1) = (n + 1)\sum_{k = 0}^n k - \sum_{k = 0}^n k^2 = \frac{n(n + 1)^2}{2} -$$

$$ $$- \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6}$$

:

$$ $$\frac{n(n + 1)(n + 2)}{6} = (n + 1)(n + 2)$$

$$$n > 0$, , $$$n = 6$.

, , . , 60x60. x , y — .

« » . « 14:45» 2 . , , , , « 14:45» , « » 3 . , $$$\frac{5}{7}$.

:

$$ $$\Pr(\xi \leq x) = \int\limits_{\pi/2}^x \frac{dt}{\sin{t}} = \int\limits_{1}^{\tan{x/2}} \frac{du}{u} = \ln{\tan{\frac{x}{2}}}$$

:

$$ $$\ln{\tan{\frac{x}{2}}} = \frac{1}{2} \Leftrightarrow \tan{\frac{x}{2}} = e^{1/2} \Leftrightarrow x = 2 \tan^{-1}{e^{1/2}}$$

. : n $$$a_0, a_1, \dots, a_{n-1}$.

- !

l r. .

$$$l$ $$$r$ :

$$ $$\sqrt[r-l+1]{a_{l} \cdot a_{l+1} \cdot \ldots \cdot a_{r}}$$

$$$n$ ($$$1 \leq n \leq 300 000$).

n $$$a_i$ ($$$0.01 \leq a_i \leq 100$) .

$$$q$ ($$$1 \leq q \leq 100 000$) — .

$$$q$ $$$l_i$ $$$r_i$ ($$$0 \leq l_i \leq r_i < n$) — $$$i$- .

6 .

.

1

2

3

, $$$xy = e^{\ln x + \ln y}$. .

. $$$(1)$, $$$O(1)$.

. sums, $$$sums[i] = a[0] + a[1] + \dots + a[i]$. $$$sums[i] = sums[i - 1] + a[i]$, $$$O(n)$. $$$l$ $$$r$ — $$$sums[r] - sums[l - 1]$. , $$$r - l + 1$. $$$O(1)$ $$$O(n)$ .

. , , , . , , $$$e$ . , $$$\ln ((a[l] \cdot ... \cdot a[r])^{\frac{1}{r - l + 1}}) = \frac{\ln a[l] \cdot \dots \cdot a[r]}{r - l + 1} = \frac{\ln a[l] + \dots + \ln a[r]}{r - l + 1}$, $$$(1)$ .

: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

$$$a$ $$$n$ . .

, .

, , .

$$$n$ ($$$1 \leq n \leq 300 000$). $$$n$ $$$a_i$ ($$$0 \leq a_i \leq 1 000 000 000$).

$$$m$ ($$$0 \leq m < n$) — , .

$$$m$ — , . , , .

1

2

3

unordered_set (C++) / HashSet (Java) / set (Python), . , , . , . , -. reverse $$$O(n)$. - $$$(1)$, $$$O(n)$.

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

, .

$$$W × H$, a b. , . , .

. , , . , .

. $$$(0, 0)$, — $$$(W, H)$. .

, .

$$$W$, $$$H$ $$$a$, $$$b$ ($$$1 \leq W$, $$$H \leq 100 000$, $$$1 \leq a \leq W$, $$$1 \leq b \leq H$).

$$$n$ ($$$0 \leq n \leq 100$) — .

$$$n$ $$$(x_{ld}, y_{ld})$ $$$(x_{ru}, y_{ru})$ ($$$0 \leq x_{ld} < x_{ru} \leq W, 0 \leq y_{ld} < y_{ru} \leq H$). , .. .

$$$(x_{ld}, y_{ld})$ $$$(x_{ru}, y_{ru})$ , . $$$a$ (, $$$b$). .

.

, .

1

2

3

, . , $$$W * n$ .

$$$x$ ( $$$0$ $$$W - a$), . , $$$x$ $$$x + a$, . , «» $$$x$ $$$x + a$, $$$y$- . , $$$(y_1, y_2)$, $$$y_1$ $$$y_2$ — $$$y$- , . $$$y_2$ — $$$y_1$.

, $$$(0, 0)$ $$$(h, h)$, . , , , . , , . , , .

. $$$O(W * n * \log n)$ $$$O(n)$ .

: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7