🚣🏾 🤵🏿 👍 Analyse complète de la première partie de l'examen dans SHAD 2020 🍪 👎🏾 🐱

salut! Je suis Azat Kalmykov, conservateur à ShAD Helper. Nous continuons notre série d'articles dans lesquels nous analysons les tâches pour entrer dans le ShAD. Cette fois, nous (moi, Nikolai Proskurin et Alexander Kurilkin) examinerons les décisions de la première étape de sélection dans le ShAD de cette année, qui s'est terminée récemment. Alors, commençons.

A. Minimum local

À quelles valeurs du paramètre une primitive de la fonction

$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}}$ a au plus un minimum local?

Décision

, — . , . , , ( ).

, , , ,

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

Déterminer à quelle valeur

$a$ cette limite est

$\frac{1}{e}$ :

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

Décision

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

À quelle descente de gradient de longueur minimale de pas ne peut pas trouver la fonction minimale

$x^4+\cos 2$ , si

$x_0=1$ ?

Décision

, :

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

Transition.

$|x_{n+1}| = |x_n - 4\lambda x_n^3| = |x_n| |1-4\lambda x_n^2|$ . En raison de l'hypothèse d'induction, nous pouvons obtenir

$x_n < 1 \Rightarrow x_n^2 < 1$ . alors

$|x_{n+1}| \leq |x_n||1-4\lambda|$ . Tout est prouvé.

En utilisant le prouvé, nous pouvons l'obtenir

$|x_n|\leq |x_0||1-4\lambda|^n = |1-4\lambda|^n$ . Puisque nous savons que

$|1-4\lambda| < 1$ alors nous obtenons cela

$|x_n|$ . .

D. Propre vecteur

Déterminer à quelles valeurs du paramètre un vecteur

$\left(\begin{array}{l} 1 \\ 1 \\ a \end{array}\right)$ est un vecteur propre de la matrice

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

Décision

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

À quelles valeurs de paramètre

$a$ déterminant maximum de la matrice inverse à cela?

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

Décision

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

Points donnés

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

$C(2,2,1)$ ainsi que l'avion

$\alpha$ :

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

$β$ :

$−x+2y+3z=0$ . Trouver les coordonnées du point

$A$ s'il est connu que sa projection orthogonale sur

$\alpha$ coïncide avec la projection du point

$B$ mais sur

$\beta$ - avec projection ponctuelle

Décision

$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

Dans la constellation lointaine de Tau-Ceti, des dominos se dressent sur chaque moitié

$0$ avant

$N$ points, et pour chaque paire de nombres

$(a,b)$ tel que

$a$ et

$b$ entier de

$0$ avant

$N$ , il existe exactement un domino contenant ces deux nombres. Le touriste spatial a volé à l'intérieur et a ramassé un jointure inversée au hasard. À quoi

$N$ l'espérance mathématique du module de la différence de nombre de points sur l'une et l'autre moitié de ce domino sera égale

$2$ ?

Décision

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

Deux amis ont décidé d'aller ensemble aux examens au SHAD et ont convenu de se rencontrer à l'entrée de 14h00 à 15h00, mais ne se sont pas mis d'accord sur l'heure. Le moment d'arrivée de chacun d'eux est réparti uniformément sur cette période de temps, mais les amis sont impatients, alors après 15 minutes d'attente, ils désespèrent d'attendre et de rentrer seuls. On sait qu'ils se sont rencontrés.

Trouvez la probabilité que les deux soient arrivés avant 14h45.

Décision

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

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

$\frac{5}{7}$ .

I. Variable aléatoire

Densité de distribution d'une variable aléatoire

$\xi$ est égal à

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

$x$ de

$\pi/2$ avant

$2 \arctan e$ et zéro pour tous les autres

$x$ .

Trouver une valeur que cette variable aléatoire ne dépasse pas avec probabilité

$\frac{1}{2}$ .

Décision

$\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. Trouver la moyenne

État

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

Décision

$(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. Supprimer le dernier

État

	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

Décision

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

$O(n)$ . -

$(1)$ ,

$O(n)$ .

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

Tableau d'affichage

État

	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

Décision

, . ,

$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

Analyse complète de la première partie de l'examen dans SHAD 2020

A. Minimum local

B. Limite

C. Minimum local

D. Propre vecteur

E. Qualificatif

F. Projections

G. Domino

H. Examen

I. Variable aléatoire

J. Trouver la moyenne

1

2

3

K. Supprimer le dernier

1

2

3

Tableau d'affichage

1

2

3

More articles: