☎️ 🗺️ 🎩 Análisis completo de la primera parte del examen en SHAD 2020 🏰 ◽️ 🌠

¡Hola! Soy Azat Kalmykov, curador de ShAD Helper. Continuamos nuestra serie de artículos en los que analizamos las tareas para ingresar al ShAD. Esta vez nosotros (yo, Nikolai Proskurin y Alexander Kurilkin) analizaremos las decisiones de la primera etapa de selección en el ShAD de este año, que finalizó recientemente. Entonces empecemos.

A. Mínimo local

A qué valores del parámetro es una antiderivada de la función

$f(x)=\left(x^{4}-(a+1) x^{3}+(a-2) x^{2}+2 a x\right) \exp ^{\frac{\sin x^{2}+2}{5 x^{2}+2}}$ tiene como máximo un mínimo local?

Decisión

, — . , . , , ( ).

, , , ,

$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$ . , .

B. Límite

Determinar a qué valor

$a$ este límite es

$\frac{1}{e}$ :

$\lim _{x \rightarrow +\inf }\left(\cos \sqrt{\frac{1}{x}}\right)^{\frac{x}{a}}$

Decisión

$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}$ .

: , , .

C. Mínimo local

A qué longitud mínima del escalón el descenso del gradiente no puede encontrar la función mínima

$x^4+\cos 2$ , Si

$x_0=1$ ?

Decisión

, :

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

D. Propio vector

Determinar a qué valores del parámetro un vector

$\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ es un vector propio de la matriz

$\left(\begin{array}{ccc} a & 1 & -1 \\ 1 & 2 & -1 \\ 0 & 0 & 1 \end{array}\right)$

Decisió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$ .

E. Calificador

A qué valores de parámetros

$a$ determinante máximo de la matriz inversa a esto?

$\left(\begin{array}{ccc} a & -7 & -3 \\ 6 & -10 & -a^{2} \\ 0 & a & 9 \end{array}\right)$

Decisión

$\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$ .

F. Proyecciones

Puntos dados

$B(1,2,−3)$ y

$C(2,2,1)$ así como el avión

$\alpha$ :

$2x−2y+z=0$ y

$β$ :

$−x+2y+3z=0$ . Encuentra las coordenadas del punto

$A$ si se sabe que su proyección ortogonal sobre

$\alpha$ coincide con la proyección del punto

$B$ pero en

$\beta$ - con proyección puntual

Decisión

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

G. Domino

En la constelación distante de Tau Ceti, en cada mitad de los nudillos de dominó hay

$0$ antes de

$N$ puntos y para cada par de números

$(a,b)$ tal que

$a$ y

$b$ entero de

$0$ antes de

$N$ , hay exactamente un dominó que contiene ambos números. El turista espacial voló y recogió un nudillo invertido al azar. En que

$N$ La expectativa matemática del módulo de la diferencia en el número de puntos en una y la otra mitad de este dominó será igual

$2$ ?

Decisión

$\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$ .

H. examen

Dos amigos decidieron ir juntos para los exámenes en el SHAD y acordaron reunirse en la entrada de 14:00 a 15:00, pero no acordaron a qué hora. El momento de llegada de cada uno de ellos se distribuye de manera uniforme durante este período de tiempo, pero los amigos están impacientes, por lo que después de 15 minutos de espera se desesperan por esperar y entran solos. Se sabe que se conocieron.

Encuentre la probabilidad de que ambos llegaron antes de las 14:45.

Decisión

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

« » . « 14:45» 2 . , , , , « 14:45» , « » 3 . ,

$\frac{5}{7}$ .

I. variable aleatoria

Densidad de distribución de una variable aleatoria.

$\xi$ es igual a

$p(x)=\frac{1}{\sin x}$ a

$x$ desde

$\pi/2$ antes de

$2 \arctan e$ y cero para todos los demás

$x$ .

Encuentre un valor que esta variable aleatoria no exceda con probabilidad

$\frac{1}{2}$ .

Decisión

$\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}}$

J. Encuentra la media

Condición

	2
	256Mb
	input.txt
	output.txt

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


8 79.02 36.68 79.83 76.00 95.48 48.84 49.95 91.91 10 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 1 7 2 7	79.020000 53.837288 61.391865 64.756970 69.986085 65.913194 63.352986 66.369195 64.735454 71.164108

2


1 1.00 1 0 0	1.000000

3


8 1.34 1.37 1.40 1.44 1.91 1.95 1.96 1.97 5 1 4 2 7 4 6 0 3 2 6	1.515518 1.752724 1.939879 1.387008 1.712233

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

Decisión

$(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

K. Eliminar último

Condición

	2
	256Mb
	input.txt
	output.txt

$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


10 1 1 5 2 4 3 3 4 2 5	5 1 5 2 4 3

2


1 1000000000	0

3


10 1 2 3 3 2 1 4 1 2 0	5 1 2 3 2 1

Decisión

unordered_set (C++) / HashSet (Java) / set (Python), . , , . , . , -. reverse

$O(n)$ . -

$(1)$ ,

$O(n)$ .

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L. Tablón de anuncios

Condición

	3
	256Mb
	input.txt
	output.txt

, .

$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


11 8 2 7 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	9 0 11 8

2


11 8 7 3 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	4 0 11 3

3


11 8 4 4 4 1 5 3 7 2 2 4 5 5 3 9 4 5 3 7 8	7 4 11 8

Decisión

, . ,

$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

Análisis completo de la primera parte del examen en SHAD 2020

A. Mínimo local

B. Límite

C. Mínimo local

D. Propio vector

E. Calificador

F. Proyecciones

G. Domino

H. examen

I. variable aleatoria

J. Encuentra la media

1

2

3

K. Eliminar último

1

2

3

L. Tablón de anuncios

1

2

3

More articles: