😘 🍩 🐄 Análise completa da primeira parte do exame no SHAD 2020 🌓 🗼 🙆🏽

Olá! Sou Azat Kalmykov, curador do ShAD Helper. Continuamos nossa série de artigos em que analisamos as tarefas para entrar no ShAD. Desta vez, nós (Nikolai Proskurin e Alexander Kurilkin) examinaremos as decisões da primeira etapa da seleção no ShAD deste ano, que terminou recentemente. Então vamos começar.

A. Mínimo local

Em que valores do parâmetro uma antiderivada da função

f (x) = (x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x) \exp^{\frac{\sin x^{2} + 2}{5 x^{2} + 2}}

$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}}$ tem no máximo um mínimo local?

Decisão

, — . , . , , ( ).

, , , ,

f (x) = x^{4} - (a + 1) x^{3} + (a - 2) x^{2} + 2 a x

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

- 1, 0, 2, a

$-1, 0, 2, a$ . ,

f (x) = (x + 1) x (x - 2) (x - a)

$f(x) = (x + 1)x(x - 2)(x - a)$ .

,

+ \to - \to + \to - \to +

$+ \to - \to + \to - \to +$ , . ,

a = - 1, 0, 2

$a = -1, 0, 2$ . , .

B. Limite

Determinar em que valor

a

$a$ determinado limite é

\frac{1}{e}

$\frac{1}{e}$ :

lim_{x \to + inf} {(\cos \sqrt{\frac{1}{x}})}^{\frac{x}{a}}

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

Decisão

a = 1

$a = 1$ .

\sqrt{\frac{1}{x}} \to 0

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

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

. , , , , . , . :

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

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

x \to + \infty

$x \to +\infty$ ,

x

$x$ , . ,

e^{- 1 / 2}

$e^{-1/2}$ . , :

lim_{x \to + \infty} {(1 - \frac{1}{2 x} + \frac{1}{24 x^{2}})}^{x} = \exp (lim_{x \to + \infty} x \ln (1 - \frac{1}{2 x} + \frac{1}{24 x^{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 (lim_{x \to + 0} \frac{\ln (1 - \frac{x}{2} + \frac{x^{2}}{24})}{x})

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

, . :

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

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

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

: , , .

C. Mínimo local

Em que descida mínima do gradiente do comprimento do passo não é possível encontrar a função mínima

x^{4} + \cos 2

$x^4+\cos 2$ , E se

x_{0} = 1

$x_0=1$ ?

Decisão

, :

x_{k} + 1 = x_{k} - λ ▽ f (x_{k})

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

.

— , .

▽ f (x_{k}) = 4 x_{k}^{3}

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

x_{0}

$x_0$ ,

x_{1}

$x_1$ :

x_{1} = x_{0} - λ 4 x_{0}^{3} = 1 - 4 λ

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

x_{1} = - 1

$x_1=-1$ ,

x_{0}

$x_0$ , . , , «» -

1

$1$

- 1

$-1$ . , ,

x_{1} = - 1 \Leftrightarrow λ = 0.5

$x_1=-1 \Leftrightarrow \lambda=0.5$ (

0

$0$ ). ,

λ

$\lambda$ .

, .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . ,

0.5 > λ > 0 \Rightarrow | 1 - 4 λ | < 1

$0.5 > \lambda > 0 \Rightarrow |1 - 4\lambda| < 1$

:

| x_{1} | = | 1 - 4 λ | \leq 1 | 1 - 4 λ | = x_{0} | 1 - 4 λ |

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

.

| x_{n + 1} | = | x_{n} - 4 λ x_{n}^{3} | = | x_{n} | | 1 - 4 λ x_{n}^{2} |

$|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 \Rightarrow x_n^2 < 1$ .

| x_{n + 1} | \leq | x_{n} | | 1 - 4 λ |

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . .

, ,

| x_{n} | \leq | x_{0} | | 1 - 4 λ |^{n} = | 1 - 4 λ |^{n}

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

| 1 - 4 λ | < 1

$|1-4\lambda| < 1$ ,

| x_{n} |

$|x_n|$ . .

D. Próprio vetor

Determine em quais valores do parâmetro um vetor

(\begin{array}{l} 1 \\ 1 \\ a \end{array})

$\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ é um autovetor da matriz

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

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

Decisão

v \neq 0

$v \neq 0$

A

$A$ ,

\exists λ

$\exists \lambda$ :

A v = λ v

$Av = \lambda v$ . :

(\begin{matrix} a & 1 & - 1 \\ 1 & 2 & - 1 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix} 1 \\ 1 \\ a \end{matrix}) = (\begin{matrix} 1 \\ 3 - a \\ a \end{matrix}) = λ (\begin{matrix} 1 \\ 1 \\ a \end{matrix})

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

λ = 1

$\lambda = 1$ , —

a = 2

$a = 2$ , , . ,

a = 2

$a = 2$ .

E. Qualificador

Em quais valores de parâmetro

a

$a$ determinante máximo da matriz inversa a isso?

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

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

Decisão

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

$\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) = 4 a^{3} - 108 = 0 \Leftrightarrow a = 3

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

, , , , ,

det (a)

$\det(a)$ ,

det (a) \geq det (3) > 0

$\det(a) \geq \det(3) > 0$

a = 3

$a = 3$ . ,

det (A^{- 1}) = det (A)^{- 1}

$\det(A^{-1}) = \det(A)^{-1}$ , ,

a = 3

$a = 3$ .

F. Projeções

Pontos dados

B (1, 2, - 3)

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

C (2, 2, 1)

$C(2,2,1)$ bem como o avião

α

$\alpha$ :

2 x - 2 y + z = 0

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

β

$β$ :

- x + 2 y + 3 z = 0

$−x+2y+3z=0$ . Encontre as coordenadas do ponto

A

$A$ se se sabe que sua projeção ortogonal sobre

α

$\alpha$ coincide com a projeção do ponto

B

$B$ mas em

β

$\beta$ - com projeção pontual

С

Decisão

A = (x, y, z)

$A = (x, y, z)$ ,

B

$B$ , ,

B

$B$ . , ,

α

$\alpha$

{\bar{n}}_{1} (2, - 2, 1)

$\overline{n}_1(2, -2, 1)$ . :

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

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

A

$A$ ,

C

$C$

β

$\beta$ . :

{\bar{n}}_{2} (- 1, 2, 3)

$\overline{n}_2(-1, 2, 3)$ , :

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

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

t_{1}

$t_1$

t_{2}

$t_2$ , :

{\begin{cases} 2 t_{1} + 1 = - t_{2} + 2 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} 3 = t_{2} + 4 \\ - 2 t_{1} + 2 = 2 t_{2} + 2 \end{cases} \Leftrightarrow {\begin{cases} t_{2} = - 1 \\ t_{1} = 1 \end{cases}

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

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

G. Domino

Na distante constelação de Tau Ceti, em cada metade da articulação dos dominós é

0

$0$ antes

N

$N$ pontos e para cada par de números

(a, b)

$(a,b)$ de tal modo que

a

$a$ e

b

$b$ inteiro de

0

$0$ antes

N

$N$ , existe exatamente um dominó que contém esses dois números. Um turista espacial chegou e pegou uma junta invertida aleatoriamente. Em que

N

$N$ a expectativa matemática do módulo da diferença no número de pontos em um e na outra metade deste dominó será igual

2

$2$ ?

Decisão

ξ

$\xi$ ,

Ω

$\Omega$

ξ (Ω)

$\xi(\Omega)$ . :

E (ξ) = \sum_{k \in ξ (Ω)} k Pr [ξ = k] = 2

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

A_{k}

$A_k$ — ,

K

$K$ ,

Pr [ξ = k] = \frac{| A_{k} |}{| Ω |}

$\Pr[\xi = k] = \frac{|A_k|}{|\Omega|}$ .

| Ω |

$|\Omega|$ , :

\sum_{k \in ξ (Ω)} k | A_{k} | = 2 | Ω |

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

| Ω |

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

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

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

.

. , 0

n

$n$ .

k

$k$ ?

n - k + 1

$n - k + 1$ : —

(0, k), (1, k + 1), \dots, (n - k, n)

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

\sum_{k \in ξ (Ω)} 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} -

$\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) (2 n + 1)}{6} = \frac{n (n + 1) (n + 2)}{6}

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

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

n > 0

$n > 0$ , ,

n = 6

$n = 6$ .

H. Exame

Dois amigos decidiram ir juntos para os exames no SHAD e concordaram em se encontrar na entrada das 14:00 às 15:00, mas não chegaram a um acordo sobre a que horas. O tempo de chegada de cada um deles é distribuído igualmente durante esse período, mas os amigos estão impacientes; portanto, após 15 minutos de espera, eles se desesperam para esperar e entrar sozinhos. Sabe-se que eles se conheceram.

Encontre a probabilidade de que ambos vieram antes das 14:45.

Decisão

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

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

\frac{5}{7}

$\frac{5}{7}$ .

I. Variável aleatória

Densidade de distribuição de uma variável aleatória

ξ

$\xi$ é igual a

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

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

x

$x$ de

π / 2

$\pi/2$ antes

2 \arctan e

$2 \arctan e$ e zero para todos os outros

x

$x$ .

Encontre um valor que essa variável aleatória não exceda com probabilidade

\frac{1}{2}

$\frac{1}{2}$ .

Decisão

Pr (ξ \leq x) = \int_{π / 2}^{x} \frac{d t}{\sin t} = \int_{1}^{\tan x / 2} \frac{d u}{u} = \ln \tan \frac{x}{2}

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

$\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. Encontre a média

Doença

	2
	256Mb
	input.txt
	output.txt

. : n

a_{0}, a_{1}, \dots, a_{n - 1}

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

- !

l r. .

l

$l$

r

$r$ :

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

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

n

$n$ (

1 \leq n \leq 300 000

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

n

a_{i}

$a_i$ (

0.01 \leq a_{i} \leq 100

$0.01 \leq a_i \leq 100$ ) .

q

$q$ (

1 \leq q \leq 100 000

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

q

$q$

l_{i}

$l_i$

r_{i}

$r_i$ (

0 \leq l_{i} \leq r_{i} < n

$0 \leq l_i \leq r_i < n$ ) —

i

$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

x y = e^{\ln x + \ln y}

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

Decisão

О (1)

$(1)$ ,

O (1)

$O(1)$ .

. sums,

s u m s [i] = a [0] + a [1] + \dots + a [i]

$sums[i] = a[0] + a[1] + \dots + a[i]$ .

s u m s [i] = s u m s [i - 1] + a [i]

$sums[i] = sums[i - 1] + a[i]$ ,

O (n)

$O(n)$ .

l

$l$

r

$r$ —

s u m s [r] - s u m s [l - 1]

$sums[r] - sums[l - 1]$ . ,

r - l + 1

$r - l + 1$ .

O (1)

$O(1)$

O (n)

$O(n)$ .

. , , , . , ,

e

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

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

$(1)$ .

: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

K. Excluir por último

Doença

	2
	256Mb
	input.txt
	output.txt

a

$a$

n

$n$ . .

, .

, , .

n

$n$ (

1 \leq n \leq 300 000

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

n

$n$

a_{i}

$a_i$ (

0 \leq a_{i} \leq 1 000 000 000

$0 \leq a_i \leq 1 000 000 000$ ).

m

$m$ (

0 \leq m < n

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

m

$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

Decisão

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

O (n)

$O(n)$ . -

О (1)

$(1)$ ,

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L. Quadro de avisos

Doença

	3
	256Mb
	input.txt
	output.txt

, .

W \times H

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

. , , . , .

.

(0, 0)

$(0, 0)$ , —

(W, H)

$(W, H)$ . .

, .

W

$W$ ,

H

$H$

a

$a$ ,

b

$b$ (

1 \leq W

$1 \leq W$ ,

H \leq 100 000

$H \leq 100 000$ ,

1 \leq a \leq W

$1 \leq a \leq W$ ,

1 \leq b \leq H

$1 \leq b \leq H$ ).

n

$n$ (

0 \leq n \leq 100

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

n

$n$

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ (

0 \leq x_{l d} < x_{r u} \leq W, 0 \leq y_{l d} < y_{r u} \leq H

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

(x_{l d}, y_{l d})

$(x_{ld}, y_{ld})$

(x_{r u}, y_{r u})

$(x_{ru}, y_{ru})$ , .

a

$a$ (,

b

$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

Decisão

, . ,

W * n

$W * n$ .

x

$x$ (

0

$0$

W - a

$W - a$ ), . ,

x

$x$

x + a

$x + a$ , . , «»

x

$x$

x + a

$x + a$ ,

y

$y$ - . ,

(y_{1}, y_{2})

$(y_1, y_2)$ ,

y_{1}

$y_1$

y_{2}

$y_2$ —

y

$y$ - , .

y_{2}

$y_2$ —

y_{1}

$y_1$ .

,

(0, 0)

$(0, 0)$

(h, h)

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

.

O (W * n * \log n)

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

O (n)

$O(n)$ .

: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7

Análise completa da primeira parte do exame no SHAD 2020

A. Mínimo local

B. Limite

C. Mínimo local

D. Próprio vetor

E. Qualificador

F. Projeções

G. Domino

H. Exame

I. Variável aleatória

J. Encontre a média

1

2

3

K. Excluir por último

1

2

3

L. Quadro de avisos

1

2

3

More articles: