Analisis penuh dari bagian pertama ujian di SHAD 2020

Halo! Saya Azat Kalmykov, kurator di ShAD Helper. Kami melanjutkan serangkaian artikel di mana kami menganalisis tugas untuk memasuki ShAD. Kali ini kita (saya, Nikolai Proskurin dan Alexander Kurilkin) akan melihat keputusan tahap seleksi pertama di ShAD tahun ini, yang berakhir baru-baru ini. Jadi mari kita mulai.

A. Minimum lokal


Pada nilai parameter apa penentu fungsi f(x)=(x4โˆ’(a+1)x3+(aโˆ’2)x2+2ax)expsinโกx2+25x2+2Apakah 5 x 2 + 2 memiliki paling banyak satu minimum lokal?

Keputusan
, โ€” . , . , , ( ).

, , , , f(x)=x4โˆ’(a+1)x3+(aโˆ’2)x2+2ax. , : โˆ’1,0,2,a. , f(x)=(x+1)x(xโˆ’2)(xโˆ’a).

, +โ†’โˆ’โ†’+โ†’โˆ’โ†’+, . , a=โˆ’1,0,2. , .

B. Batas


Tentukan berapa nilainya abatas yang diberikan adalah1e :

limxโ†’+inf(cosโก1x)xa


Keputusan
, a=1. 1xโ†’0, :

cosโก1x=1โˆ’12!x+14!x2โˆ’16!x3+โ€ฆ



. , , , , . , . :

1โˆ’12x<cosโก1x<1โˆ’12x+124x2



xโ†’+โˆž, x, . , eโˆ’1/2. , :

limxโ†’+โˆž(1โˆ’12x+124x2)x=expโก(limxโ†’+โˆžxlnโก(1โˆ’12x+124x2))=


=expโก(limxโ†’+0lnโก(1โˆ’x2+x224)x)



, . :

limxโ†’+โˆž(cosโก1x)x=eโˆ’1/2โ‡’limxโ†’+โˆž(cosโก1x)x/a=eโˆ’1/2a



a=12.

: , , .

C. Minimum lokal


Pada penurunan gradien panjang langkah minimum apa tidak dapat menemukan fungsi minimum x4+cosโก2, jika x0=1?

Keputusan
, :

xk+1=xkโˆ’ฮปโ–ฝf(xk)

.

โ€” , .

โ–ฝf(xk)=4xk3



x0, x1:

x1=x0โˆ’ฮป4x03=1โˆ’4ฮป



, x1=โˆ’1, x0, . , , ยซยป - 1โˆ’1. , , x1=โˆ’1โ‡”ฮป=0.5( 0). , ฮป.

, . |xn+1|โ‰ค|xn||1โˆ’4ฮป|. , 0.5>ฮป>0โ‡’|1โˆ’4ฮป|<1

:|x1|=|1โˆ’4ฮป|โ‰ค1|1โˆ’4ฮป|=x0|1โˆ’4ฮป|

. |xn+1|=|xnโˆ’4ฮปxn3|=|xn||1โˆ’4ฮปxn2|. xn<1โ‡’xn2<1. |xn+1|โ‰ค|xn||1โˆ’4ฮป|. .

, , |xn|โ‰ค|x0||1โˆ’4ฮป|n=|1โˆ’4ฮป|n. , |1โˆ’4ฮป|<1, |xn|. .


D. Vektor sendiri


Tentukan pada nilai parameter mana vektor (11a)adalah vektor eigen dari matriks

(a1โˆ’112โˆ’1001)



Keputusan
, vโ‰ 0A, โˆƒฮป: Av=ฮปv. :

(a1โˆ’112โˆ’1001)(11a)=(13โˆ’aa)=ฮป(11a)



. ฮป=1, โ€” a=2, , . , a=2.

E. Kualifikasi


Pada nilai parameter apa apenentu maksimum dari matriks terbalik ini?

(aโˆ’7โˆ’36โˆ’10โˆ’a20a9)



Keputusan
:

det(a)=|aโˆ’7โˆ’36โˆ’10โˆ’a20a9|=a|โˆ’10โˆ’a2a9|โˆ’6|โˆ’7โˆ’3a9|=a4โˆ’108a+376



detโ€ฒ(a)=4a3โˆ’108=0โ‡”a=3



, , , , , det(a), det(a)โ‰ฅdet(3)>0a=3. , det(Aโˆ’1)=det(A)โˆ’1, , a=3.

F. Proyeksi


Poin yang diberikan B(1,2,โˆ’3)dan C(2,2,1)serta pesawat ฮฑ:2xโˆ’2y+z=0 dan ฮฒ:โˆ’x+2y+3z=0. Temukan koordinat titikAjika diketahui bahwa proyeksi orthogonal ke atas ฮฑbertepatan dengan proyeksi titik Btapi terus ฮฒ- dengan proyeksi titik .

Keputusan
A=(x,y,z), B, , B. , , ฮฑnยฏ1(2,โˆ’2,1). :

{x=2t1+1y=โˆ’2t1+2z=t1โˆ’3



, A, Cฮฒ. : nยฏ2(โˆ’1,2,3), :

{x=โˆ’t2+2y=โˆ’2t2+2z=3t2+1



. t1t2, :

{2t1+1=โˆ’t2+2โˆ’2t1+2=2t2+2โ‡”{3=t2+4โˆ’2t1+2=2t2+2โ‡”{t2=โˆ’1t1=1



, , A(3,0,โˆ’2), .

G. Domino


Di konstelasi Tau-Ceti yang jauh, domino berdiri 0sebelum Npoin, dan untuk setiap pasangan angka (a,b)seperti yang adan bkeseluruhan dari 0sebelum N, tepat ada satu domino yang mengandung kedua angka ini. Turis antariksa itu terbang masuk dan mengambil buku jari terbalik secara acak. Pada apaN ekspektasi matematis dari modul perbedaan dalam jumlah poin pada satu dan setengah lainnya dari domino ini akan sama 2?

Keputusan
ฮพ, ฮฉฮพ(ฮฉ). :

E(ฮพ)=โˆ‘kโˆˆฮพ(ฮฉ)kPr[ฮพ=k]=2



Akโ€” , K, Pr[ฮพ=k]=|Ak||ฮฉ|. |ฮฉ|, :

โˆ‘kโˆˆฮพ(ฮฉ)k|Ak|=2|ฮฉ|



|ฮฉ|. -, . -, , . ,

|ฮฉ|=n+1+n(n+1)2

.

. , 0 n. k? nโˆ’k+1: โ€” (0,k),(1,k+1),โ€ฆ,(nโˆ’k,n). :

โˆ‘kโˆˆฮพ(ฮฉ)k|Ak|=โˆ‘k=0nk(nโˆ’k+1)=(n+1)โˆ‘k=0nkโˆ’โˆ‘k=0nk2=n(n+1)22โˆ’


โˆ’n(n+1)(2n+1)6=n(n+1)(n+2)6



:

n(n+1)(n+2)6=(n+1)(n+2)



n>0, , n=6.

H. Ujian


Dua teman memutuskan untuk pergi bersama untuk ujian di SHAD dan setuju untuk bertemu di pintu masuk dari pukul 14: 00-15: 00, tetapi tidak setuju pada jam berapa. Waktu kedatangan masing-masing didistribusikan secara merata selama periode waktu ini, tetapi teman-teman tidak sabar, jadi setelah 15 menit menunggu mereka putus asa untuk menunggu dan datang sendiri. Diketahui bahwa mereka bertemu.

Temukan kemungkinan bahwa keduanya datang sebelum pukul 14:45.

Keputusan
, , . , 60x60. x , y โ€” .

ยซ ยป . ยซ 14:45ยป 2 . , , , , ยซ 14:45ยป , ยซ ยป 3 . , 57.

I. Variabel acak


Kepadatan distribusi dari variabel acak ฮพadalah sama dengan p(x)=1sinโกxdi xdari ฯ€/2sebelum 2arctanโกedan nol untuk yang lainnya x.

Temukan nilai yang tidak bisa dilewati oleh variabel acak ini12.

Keputusan
:

Pr(ฮพโ‰คx)=โˆซฯ€/2xdtsinโกt=โˆซ1tanโกx/2duu=lnโกtanโกx2



:

lnโกtanโกx2=12โ‡”tanโกx2=e1/2โ‡”x=2tanโˆ’1โกe1/2



J. Temukan artinya


Kondisi
2
256Mb
input.txt
output.txt

. : n a0,a1,โ€ฆ,anโˆ’1.

- !

l r. .

lr:

alโ‹…al+1โ‹…โ€ฆโ‹…arrโˆ’l+1




n(1โ‰คnโ‰ค300โ€ฏ000).

n ai(0.01โ‰คaiโ‰ค100) .

q(1โ‰คqโ‰ค100โ€ฏ000) โ€” .

qliri(0โ‰คliโ‰คri<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=elnโกx+lnโกy. .

Keputusan
. (1), O(1).

. sums, sums[i]=a[0]+a[1]+โ‹ฏ+a[i]. sums[i]=sums[iโˆ’1]+a[i], O(n). lrโ€” sums[r]โˆ’sums[lโˆ’1]. , rโˆ’l+1. O(1)O(n).

. , , , . , , e. , lnโก((a[l]โ‹…...โ‹…a[r])1rโˆ’l+1)=lnโกa[l]โ‹…โ‹ฏโ‹…a[r]rโˆ’l+1=lnโกa[l]+โ‹ฏ+lnโกa[r]rโˆ’l+1, (1).

: gist.github.com/Azatik1000/0b0d8496785169a8ac0d35a8c9e8e59f

K. Hapus yang terakhir


Kondisi
2
256Mb
input.txt
output.txt

an. .

, .

, , .


n(1โ‰คnโ‰ค300โ€ฏ000). nai(0โ‰คaiโ‰ค1โ€ฏ000โ€ฏ000โ€ฏ000).


m(0โ‰ค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


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

: gist.github.com/Azatik1000/2fef745e23c23eb020f21878980cae08

L. papan buletin


Kondisi
3
256Mb
input.txt
output.txt

, .

Wร—H, a b. , . , .

. , , . , .

. (0,0), โ€” (W,H). .

, .


W, Ha, b(1โ‰คW, Hโ‰ค100โ€ฏ000, 1โ‰คaโ‰คW, 1โ‰คbโ‰คH).

n(0โ‰คnโ‰ค100) โ€” .

n(xld,yld)(xru,yru)(0โ‰คxld<xruโ‰คW,0โ‰คyld<yruโ‰คH). , .. .


(xld,yld)(xru,yru), . 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


Keputusan
, . , Wโˆ—n.

x( 0Wโˆ’a), . , xx+a, . , ยซยป xx+a, y- . , (y1,y2), y1y2โ€” y- , . y2โ€” y1.

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

. O(Wโˆ—nโˆ—logโกn)O(n).

: gist.github.com/Azatik1000/2c07ebdd866ce20a4b5f5e6ee7408ad7

All Articles