Loading [MathJax]/extensions/tex2jax.js

���������� �� �������� �������� � ������� � �������� �����

A: ���������� �� ������?

��� ������ �����. ����������, �������� �� �� ��������� ������������ (�� ���� ����� ��, ��� ������ ������� ����� ������� ������ �����������).

������� �������� � ���� ������� bool is_ascending(const vector<int> & a). � ������ ������� ������ ���� ���� ���� while, �� ���������� ��������� ������� � ������ — ����������� ����� ��������� ������. ����� � ������� �� ������ ���� ������� ����������� �������� �� ������ ��������� ����� ������� 0, 1 � �.�.

�� �������� ������ ������ ���� �������.

���� �����
3
1 7 9
YES

B: k-� ���������

��� ������ �����, ����� \(key\) � ����������� ����� \(k\). ������� ������ \(k\)-�� �� ����� ��������� � ������� ����� \(key\).

������� �������� � ���� ������� int kth_appearance(const vector<int> & a, int key, int k). ������� ������ ���������� ������ \(k\)-�� �� ����� ��������� � ������� ����� \(key\). ���� ����� \(key\) ����������� � ������� ����� \(k\) ���, ������� ������ ������� -1.

������ ������ �������� �� ����������� ������ �� �������. ����������� ����� ��������� ������.

�� �������� ������ ������ ���� �������.

���� �����
10
1 2 1 3 2 3 2 3 2 2
3 2
5
4
1 1 1 1
1 5
-1

���������� �� ���������� ������������ ���������� ����������

C: ���������� �������

��� ������ ����� �����. ������������ ��� � ������� ������������� ��������.

������ ��� ������ ��� ������ ��������� ���������� �������. ������� �������� � ���� ������� void selection_sort(vector<int> & a).

�� �������� ������ ������ ���� �������.

��������������� �������� ������������ ������.

���� �����
5
1 4 2 3 4
4 4 3 2 1

D: ���������� ��������

��� ������ ����� �����. ������������ ��� � ������� ���������� ��������.

������ ��� ������ ��� ������ ��������� ���������� ��������. ������� �������� � ���� ������� void insertion_sort(vector<int> & a).

�� �������� ������ ������ ���� �������.

��������������� �������� ������������ ������.

���� �����
5
1 4 2 3 4
1 2 3 4 4

E: ���������� ���������

��� ������ ����� �����. ������������ ��� � ������� ������������� ��������.

������ ��� ������ ��� ������ ��������� ����������� ����������. ������� �������� � ���� ������� void bubble_sort(vector<int> & a).

�� �������� ������ ������ ���� �������.

��������������� �������� ������������ ������.

���� �����
5
1 4 2 3 4
4 4 3 2 1

���������� �� ���������� ����������� ����������

�������� ��������, ��� � ��������� ������� ���������� ������ ����� ����� ������, ��� ��� ������� ����� �� ��������� ������������ ������������ ��������� ����������. ����������� ����������� ������� sort ���������� STL.

F: �������� ������

��������� ������������� ��������, ��� ����� �� ����� ������ ���������������� ������. ������, ����� �����, ���� �� ����� ��������� �����, ����� ���� ������ ��� ��������� ����� ������������ ������.

��������, ����� ����� �������� ����� ������� ������������.

�������� ���������, ������� �� �������� ���������� � ������������� � ���������� ������ �� �������� ����� ��������� ������������ ����� �������������, ��� ������ ����� ��������� � �����, ��� ���� ��������� ��������� ����� ��� ����� ����� �����.

��������� �������� �� ���� � ����� ������ ����� \(S\)  ������ ���������� ����� �� �����, � ����� \(N\) — ���������� �������������, ����� ����� ���� \(N\) ����� — ����� ������ ������� ������������, ���������� ������ � ��������� ������.

�������� ���������� ���������� �������������, ��� ������ ����� ���� �������� � �����.

����������� ����������� ����������. ������� ������ ����� ��������� ����������� ���������� + \(O(N)\). ������� �� ������ �������������� �������� ������ ����� ���������� � ����������.

���� �����
100 2
200
50
1
100 3
50
30
50
2

G: �����

����� ������������� ��������� �������� ����� ����� �������� �����, ����� �������� ����������� �� �����. �� ������� \(N\) ����� —����� �������, ����� � ���� �����������. ������ ����� ��� ���������, ���������, ��� � ������� �������� ����� ���� ����� �� 1 ��������.

�������� �����, ������ ���������� ������� ���������� �� ������ �� ���� (� ���������, ��� ���������� ����� � ������ ������������, ������� ������ ��������� ���� ����������� �� ����� ������). ������ �������� ����� ����������, ������� �������� ��������� �� ��������� ���� �����������. �����������, �������� ����� ��������� ��� ����� ������� �����.

� ������ ������ �������� ����� ����������� \(N\le10^5\), �� ������ ������ �������� \(N\) ����� ����� ������, �������� ���������� � ���������� �� ������ �� ����� ����������� ��������. � ������� ������ �������� \(N\) ����� — ������ �� ������ ������ ��������� � �����.

�������� ���� ����� ����� — ���������� �����, ������� �������� ��������� �� �������� ���� �����������.

���� �����
3
10 20 30
50 20 30
1700

H: ������

� ������������ ���������� ��������������� �����: “������� ��� ����� ������, ������ ��������� ���������*”, � ����� ������ ������� ��������� “* — �� ���� ��������� ���� ������� ������������ ��� �������� �������”.

����, ��� � �����������, �����������, ����� ������ �� ����� ������, � �����, ������� ��� �����. �������� ��� ���������� ����������� ����� �����, ������� ��� ����� ����� � �����, ����� � ����� ����� ���������� ����������� ���� �������.

��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����� — ��������� ��������� ����� �������. ��� ��������� — ����������� �����, �� ����������� \(10000\).

�������� ���� ����� — ����� �����, ������� ���� ������ ����� � ����� � ����������� (���������� ���������).

���� ����� ���������
6
1 5 4 3 5 7
19
���� ������� ������� ����� ����� � �������� ���������� 1, 3 � 4 � �������� 7 ������ � ����� ���������� 1 ������� � �������, � ����� ����� ������ � ����������� � ����� ������ ���������� 5 � 7, ��� ���� ����� ���������� 5 ������� � �������.
5
3 15 25 8 8
51
���� � ������ ����� � ����������� ����� ������ ���������� 15 � 25 ������, � �������� ������� ���� ����� ���������� 8 ������. � �� ������ ����� � ����������� ����� ������ ���������� 3 � 8, �� ���� �������� �������.

I: ���������� ��������� �����

��� ������ �����. ����������, ������� � ��� ��������� �����.

��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����������� �����, �� ����������� \(10^9\).

���� �����
5
1 7 9 7 1
3

J: ��� ��������� �����

��� ������ ����������� �����, ���������� �� ����� ���� ���������. ������� � ��� ��� ��������� ���� � ����� ����� (�� ���� ��� ����� � ���������� ���������).

�������� ��� ����� � ������� ����������.

��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����������� �����, �� ����������� \(10^9\).

���� �����
4
9 4 1 6
4 6

K: �������

���� ����� �������������� � ����������� ������� ������ ������� ���� ����� �� ��������� �����. � ��� ���� \(N\) �����������, ��� ������� �� ��� ��� ������ ������ ��� ��������� \(P_i\). ������� �������� ����� ����� � ����� �� ���������� � ���������� �� ����� ����������� ���, ����� � ���������� �������� ����������� ��������� ���������. �� ������� ������ � ������ ������� ������ �� �������� �������� ����� �������� �� ������ ���������.

������ ������ ������� ������ �������� ����� \(N\le10^5\)—  ���������� �����������. ������ ������ �������� \(N\) ����������� ����� \(X_1\), ..., \(X_N\) — ������� ��������� �����������. ������ ������ �������� ���� ����� \(Y\) — ��������� �������.

�������� ���� �������������� ����� — ������������ ����� �����, ������� ����� ��������� � ������� � ���������� ���������.

���� �����
2
5 10
5
7.5
3
1 3 2
0
2.125
1
1
2
2.0

L: ������ � ���

��������� � ��� ���������� ��������� ���������� � ���������� �������� �������. ���������� ���������� ������ ����� �������.

��� ���������� ������� �� \(N\) ����� (������������� ������ �� �����������), ������ ������ ����� ������ ������������� � �������� ����������. ������� � ������ ������ ���������� ����������� �� ������������� �������, ���� ������ ����� �������� ����������� ������ ������������� “��”, �� ������������� ���� ������ � �������� ���������� �������� ”��“ �� ����� ���� ������. ������� �����������, ���� ������ ����� �������� ���������� (�� ���� �����) ������������� “��”.

��� ����� ������� ������� ����� ���� ������� ��������� ����������, ���� ���� “��” ����������� ����� �������� �� ������ ����� �����������.

������ ������ ������� ������ �������� ����� \(N\le10^5\) — ���������� �����. ������ ������ �������� \(N\) ����� — ������� �����.

��������� ������ ������� ����������� ���������� �����������, ������� ����� ������������� “��”, ���� � ����� ������� ���� ������� ��������� ����������.

���� �����
3
5 5 7
6
5
4 2 1 3 7
5

M: ������������� ��������

� ��������� ������ �� ������ ����� ����������� \(n\) �����. \(i\)-� ��� ����� ��������������� ��������� \(x_i\) — ����������� �� ������ ����� �� ����, ����� �������, ���������� ����� ����� ������ \(i\) � \(j\) ����� \(|x_i-x_j|\).

� ����� �� ���� ����� ���������� ������� ������� ����� �������, ����� ��������� ���������� �� �������� �� ��������� ����� ���� ����������.

������ ������ ������� ������ �������� ����� \(N\le10^5\) — ���������� �����. ������ ������ �������� \(N\) ����� — ���������� �����.

��������� ������ ������� ���������� ����, � ������� ���������� ������� �������. ���� ��������� ������� ���������, ���������� ������� ����� �� ���.

��������. ��� ����� ������� ������.

���� �����
4
1 2 3 4
2

N: ���������

� ������ ������ \(N\) �������. �������� ������������ ������� �������� ������� �� �� \(R\) ������ �� \(C\) ������� � ������ � ��������� �� ��������� (\(N = RC\)).

��� ������� �� ���������� ����� ���������� ���������� ������. ������ ������ ������������ ����� ��� ����� ����� �������. ��� ���� ������ ����� ��� �������, ��� ����� ����������� ���� ������ ���� �������.

������ ���������� ������� ����� �������� �������� ����� ������ ������ �������� � ������ ������ ������� ������ ���� ������� (���� � ������� ������ ���� �������, �� ��� ������� ����� 0). �������� ������������ ����� ������������ ������� ���, ����� ������������ �� ����� ���������� �������������� ������ ���� ����������. �������� ��� � ����!

���������� ��������� ������. ����� � ������ 8 �������, ���� ������� � ����������� ����� 170, 205, 225, 190, 260, 130, 225, 160, � ���������� ������������ ��� ������� �� ������ �������� � ������. ����� ����� �� ��������� �������� �����:

1 �������: ���� � ������ 225, 205, 225, 260.

2 �������: ���� � ������ 160, 190, 170, 130.

��� ���� ������������ ����� ���������� ����� �� ������ �������, ��� ����� ����� 60, � ��� ��������� ��������� ���������.

������ ������ ������� ������ �������� ��� ����������� ����� \(R\) � \(C\) — ���������� ������ � ���������� ������� � ������ �������. ����� �������� \(N = RC\) ����� ����� �� ������ ����� � ������ — ���� ������� �� \(N\) ��������.

�������� ���� ����� — ���������� ��������� �������� ������������� ����� ���������� �������������� ������.

���� �����
2 4
170
205
225
190
260
130
225
160
60

O: ������� �������

� ������� �������� ��������� ����� ������� �������. ��������, ��� ���� ���� ����� ����� ������ �� ������, ���� ��� ���� �� �� ��� ������� ������. � ������� ������ ����������. ��������� ����������, ����� ���������� ���������� ��� ����� ������ ���������� ��� �������� ���, ����� �� ���� ������ �� ��� ������������.

������ ������ ������� ������ �������� ���������� ��� ����� � �������� \(N\le 10^5\) � ������ ���� ���������� \(S\). �� ������ ������ �������� \(N\) ����� — ������� ������ ���� ����� � �������� ����� ������. ��� ������� — ����������� �����, �� ������������� \(10^9\). ���������� �� ������ ������ �����, ������ ������� ������ \(S\).

�������� ������������ ����� —������������ ���������� ��� �����, ������� ������ ������ ����������.

���� �����
2 60
60 63
2
5 35
40 35 41 30 42
2

P: ������

� 179 ����� ���� ����� ������� ����� ������ ��������. �������� ����� ������ ������ ������ �������, ������� �� ������ �������� ��� ����. �������� ������� ���� ������� � ������� ��� ����������. ����������, ����� ���������� ����� ���������� ������ ������������ ����� ����������.

������ ������ ������� ������ �������� ���������� ������� \(N \le 10^5\). �� ������ ������ �������� \(N\) ����� — ������� �������. � ������� ������ �������� ���������� ��������� \(M \le 10^5\). � ��������� ������ �������� \(M\) ����� — ������� ��� ����������. ��� ������� — ����������� �����, �� ������������� \(10^9\).

�������� ������������ ����� — ���������� ���������� ����������, ������� ������ ����� �� �����.

���� �����
4
41 40 39 42
3
42 41 42
2

Q: �������������� �����

���� \(N\) �����, ����� ������� — ����� �����. ���������� ����������� ������������� ����� �����, ������� ������ ������������ �� �������� ����� ��� ������ ������-�� ������������ ������� ������ �����.

��������� �������� �� ���� ����� \(N\le 10^5\), ����� \(N\) ����� — ����� ����� (����� �����, �� ������������� \(10^9\)). ��������� ������ ������� ���� ����� — ������� �����.

�������� ��������, ��� ��� �������� ������ � ���� ������ ������������ ���� int.

���� �����
4
1 1 5 1
4
4
1 2 4 8
16

R: World of tanks

��� ���� ��������� �� ���� ���� ���, ����� �������, ��� �� ����� � ������ ���������. ���� ��� ������������ �� ������ � �� ��� ��������� ����� �����������, ������� ����� ������� ������� � �������������� ������������. �� ������ �������� �� ������, � ���� ����������� ������ ���������� ��� ����� �����������, ����������� �� ����� ��������. ����������, ����� ���������� ����� ��������� ���������� ��� ����������� ���� ������ ����������.

������ ������ ������� ������ �������� ���������� ������ \(N\le 10^5\). ��������� \(N\) ����� �������� �� ��� ����� \(x_i\) � \(y_i\) — ���������� ������ (\(0\lt x_i\le 10^3\), \(-10^3\le y_i\le 10^3\)).

��������� ������ ������� ���� ����� — ����������� ���������� ���������.

���� �����
4
1 0
1 -1
2 2
3 3
3