��� ������ �����. ����������, �������� �� �� ��������� ������������ (�� ���� ����� ��, ��� ������ ������� ����� ������� ������ �����������).
������� �������� � ���� ������� bool is_ascending(const vector<int> & a)
.
� ������ ������� ������ ���� ���� ���� while, �� ���������� ���������
������� � ������ — ����������� ����� ��������� ������.
����� � ������� �� ������ ���� ������� ����������� ��������
�� ������ ��������� ����� ������� 0, 1 � �.�.
�� �������� ������ ������ ���� �������.
���� | ����� |
---|---|
3 |
YES |
��� ������ �����, ����� \(key\) � ����������� ����� \(k\). ������� ������ \(k\)-�� �� ����� ��������� � ������� ����� \(key\).
������� �������� � ���� ������� int kth_appearance(const vector<int> & a, int key, int k)
.
������� ������ ���������� ������ \(k\)-�� �� ����� ��������� � �������
����� \(key\). ���� ����� \(key\) ����������� � ������� �����
\(k\) ���, ������� ������ ������� -1.
������ ������ �������� �� ����������� ������ �� �������. ����������� ����� ��������� ������.
�� �������� ������ ������ ���� �������.
���� | ����� |
---|---|
10 |
5 |
4 |
-1 |
��� ������ ����� �����. ������������ ��� � ������� ������������� ��������.
������ ��� ������ ��� ������ ��������� ���������� �������.
������� �������� � ���� ������� void selection_sort(vector<int> & a)
.
�� �������� ������ ������ ���� �������.
��������������� �������� ������������ ������.
���� | ����� |
---|---|
5 |
4 4 3 2 1 |
��� ������ ����� �����. ������������ ��� � ������� ���������� ��������.
������ ��� ������ ��� ������ ��������� ���������� ��������.
������� �������� � ���� ������� void insertion_sort(vector<int> & a)
.
�� �������� ������ ������ ���� �������.
��������������� �������� ������������ ������.
���� | ����� |
---|---|
5 |
1 2 3 4 4 |
��� ������ ����� �����. ������������ ��� � ������� ������������� ��������.
������ ��� ������ ��� ������ ��������� ����������� ����������.
������� �������� � ���� ������� void bubble_sort(vector<int> & a)
.
�� �������� ������ ������ ���� �������.
��������������� �������� ������������ ������.
���� | ����� |
---|---|
5 |
4 4 3 2 1 |
�������� ��������, ��� � ��������� ������� ���������� ������ ����� ����� ������,
��� ��� ������� ����� �� ��������� ������������ ������������ ��������� ����������.
����������� ����������� ������� sort
���������� STL.
��������� ������������� ��������, ��� ����� �� ����� ������ ���������������� ������. ������, ����� �����, ���� �� ����� ��������� �����, ����� ���� ������ ��� ��������� ����� ������������ ������.
��������, ����� ����� �������� ����� ������� ������������.
�������� ���������, ������� �� �������� ���������� � ������������� � ���������� ������ �� �������� ����� ��������� ������������ ����� �������������, ��� ������ ����� ��������� � �����, ��� ���� ��������� ��������� ����� ��� ����� ����� �����.
��������� �������� �� ���� � ����� ������ ����� \(S\) ������ ���������� ����� �� �����, � ����� \(N\) — ���������� �������������, ����� ����� ���� \(N\) ����� — ����� ������ ������� ������������, ���������� ������ � ��������� ������.
�������� ���������� ���������� �������������, ��� ������ ����� ���� �������� � �����.
����������� ����������� ����������. ������� ������ ����� ��������� ����������� ���������� + \(O(N)\). ������� �� ������ �������������� �������� ������ ����� ���������� � ����������.
���� | ����� |
---|---|
100 2 |
1 |
100 3 |
2 |
����� ������������� ��������� �������� ����� ����� �������� �����, ����� �������� ����������� �� �����. �� ������� \(N\) ����� —����� �������, ����� � ���� �����������. ������ ����� ��� ���������, ���������, ��� � ������� �������� ����� ���� ����� �� 1 ��������.
�������� �����, ������ ���������� ������� ���������� �� ������ �� ���� (� ���������, ��� ���������� ����� � ������ ������������, ������� ������ ��������� ���� ����������� �� ����� ������). ������ �������� ����� ����������, ������� �������� ��������� �� ��������� ���� �����������. �����������, �������� ����� ��������� ��� ����� ������� �����.
� ������ ������ �������� ����� ����������� \(N\le10^5\), �� ������ ������ �������� \(N\) ����� ����� ������, �������� ���������� � ���������� �� ������ �� ����� ����������� ��������. � ������� ������ �������� \(N\) ����� — ������ �� ������ ������ ��������� � �����.
�������� ���� ����� ����� — ���������� �����, ������� �������� ��������� �� �������� ���� �����������.
���� | ����� |
---|---|
3 |
1700 |
� ������������ ���������� ��������������� �����: “������� ��� ����� ������, ������ ��������� ���������*”, � ����� ������ ������� ��������� “* — �� ���� ��������� ���� ������� ������������ ��� �������� �������”.
����, ��� � �����������, �����������, ����� ������ �� ����� ������, � �����, ������� ��� �����. �������� ��� ���������� ����������� ����� �����, ������� ��� ����� ����� � �����, ����� � ����� ����� ���������� ����������� ���� �������.
��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����� — ��������� ��������� ����� �������. ��� ��������� — ����������� �����, �� ����������� \(10000\).
�������� ���� ����� — ����� �����, ������� ���� ������ ����� � ����� � ����������� (���������� ���������).
���� | ����� | ��������� |
---|---|---|
6 |
19 |
���� ������� ������� ����� ����� � �������� ���������� 1, 3 � 4 � �������� 7 ������ � ����� ���������� 1 ������� � �������, � ����� ����� ������ � ����������� � ����� ������ ���������� 5 � 7, ��� ���� ����� ���������� 5 ������� � �������. |
5 |
51 |
���� � ������ ����� � ����������� ����� ������ ���������� 15 � 25 ������, � �������� ������� ���� ����� ���������� 8 ������. � �� ������ ����� � ����������� ����� ������ ���������� 3 � 8, �� ���� �������� �������. |
��� ������ �����. ����������, ������� � ��� ��������� �����.
��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����������� �����, �� ����������� \(10^9\).
���� | ����� |
---|---|
5 |
3 |
��� ������ ����������� �����, ���������� �� ����� ���� ���������. ������� � ��� ��� ��������� ���� � ����� ����� (�� ���� ��� ����� � ���������� ���������).
�������� ��� ����� � ������� ����������.
��������� �������� �� ���� ����� \(N\) (\(1\le N\le 10^5\)), � ����� \(N\) ����������� �����, �� ����������� \(10^9\).
���� | ����� |
---|---|
4 |
4 6 |
���� ����� �������������� � ����������� ������� ������ ������� ���� ����� �� ��������� �����. � ��� ���� \(N\) �����������, ��� ������� �� ��� ��� ������ ������ ��� ��������� \(P_i\). ������� �������� ����� ����� � ����� �� ���������� � ���������� �� ����� ����������� ���, ����� � ���������� �������� ����������� ��������� ���������. �� ������� ������ � ������ ������� ������ �� �������� �������� ����� �������� �� ������ ���������.
������ ������ ������� ������ �������� ����� \(N\le10^5\)— ���������� �����������. ������ ������ �������� \(N\) ����������� ����� \(X_1\), ..., \(X_N\) — ������� ��������� �����������. ������ ������ �������� ���� ����� \(Y\) — ��������� �������.
�������� ���� �������������� ����� — ������������ ����� �����, ������� ����� ��������� � ������� � ���������� ���������.
���� | ����� |
---|---|
2 |
7.5 |
3 |
2.125 |
1 |
2.0 |
��������� � ��� ���������� ��������� ���������� � ���������� �������� �������. ���������� ���������� ������ ����� �������.
��� ���������� ������� �� \(N\) ����� (������������� ������ �� �����������), ������ ������ ����� ������ ������������� � �������� ����������. ������� � ������ ������ ���������� ����������� �� ������������� �������, ���� ������ ����� �������� ����������� ������ ������������� “��”, �� ������������� ���� ������ � �������� ���������� �������� ”��“ �� ����� ���� ������. ������� �����������, ���� ������ ����� �������� ���������� (�� ���� �����) ������������� “��”.
��� ����� ������� ������� ����� ���� ������� ��������� ����������, ���� ���� “��” ����������� ����� �������� �� ������ ����� �����������.
������ ������ ������� ������ �������� ����� \(N\le10^5\) — ���������� �����. ������ ������ �������� \(N\) ����� — ������� �����.
��������� ������ ������� ����������� ���������� �����������, ������� ����� ������������� “��”, ���� � ����� ������� ���� ������� ��������� ����������.
���� | ����� |
---|---|
3 |
6 |
5 |
5 |
� ��������� ������ �� ������ ����� ����������� \(n\) �����. \(i\)-� ��� ����� ��������������� ��������� \(x_i\) — ����������� �� ������ ����� �� ����, ����� �������, ���������� ����� ����� ������ \(i\) � \(j\) ����� \(|x_i-x_j|\).
� ����� �� ���� ����� ���������� ������� ������� ����� �������, ����� ��������� ���������� �� �������� �� ��������� ����� ���� ����������.
������ ������ ������� ������ �������� ����� \(N\le10^5\) — ���������� �����. ������ ������ �������� \(N\) ����� — ���������� �����.
��������� ������ ������� ���������� ����, � ������� ���������� ������� �������. ���� ��������� ������� ���������, ���������� ������� ����� �� ���.
��������. ��� ����� ������� ������.
���� | ����� |
---|---|
4 |
2 |
� ������ ������ \(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 |
60 |
� ������� �������� ��������� ����� ������� �������. ��������, ��� ���� ���� ����� ����� ������ �� ������, ���� ��� ���� �� �� ��� ������� ������. � ������� ������ ����������. ��������� ����������, ����� ���������� ���������� ��� ����� ������ ���������� ��� �������� ���, ����� �� ���� ������ �� ��� ������������.
������ ������ ������� ������ �������� ���������� ��� ����� � �������� \(N\le 10^5\) � ������ ���� ���������� \(S\). �� ������ ������ �������� \(N\) ����� — ������� ������ ���� ����� � �������� ����� ������. ��� ������� — ����������� �����, �� ������������� \(10^9\). ���������� �� ������ ������ �����, ������ ������� ������ \(S\).
�������� ������������ ����� —������������ ���������� ��� �����, ������� ������ ������ ����������.
���� | ����� |
---|---|
2 60 |
2 |
5 35 |
2 |
� 179 ����� ���� ����� ������� ����� ������ ��������. �������� ����� ������ ������ ������ �������, ������� �� ������ �������� ��� ����. �������� ������� ���� ������� � ������� ��� ����������. ����������, ����� ���������� ����� ���������� ������ ������������ ����� ����������.
������ ������ ������� ������ �������� ���������� ������� \(N \le 10^5\). �� ������ ������ �������� \(N\) ����� — ������� �������. � ������� ������ �������� ���������� ��������� \(M \le 10^5\). � ��������� ������ �������� \(M\) ����� — ������� ��� ����������. ��� ������� — ����������� �����, �� ������������� \(10^9\).
�������� ������������ ����� — ���������� ���������� ����������, ������� ������ ����� �� �����.
���� | ����� |
---|---|
4 |
2 |
���� \(N\) �����, ����� ������� — ����� �����. ���������� ����������� ������������� ����� �����, ������� ������ ������������ �� �������� ����� ��� ������ ������-�� ������������ ������� ������ �����.
��������� �������� �� ���� ����� \(N\le 10^5\), ����� \(N\) ����� — ����� ����� (����� �����, �� ������������� \(10^9\)). ��������� ������ ������� ���� ����� — ������� �����.
�������� ��������, ��� ��� �������� ������ � ���� ������ ������������ ���� int
.
���� | ����� |
---|---|
4 |
4 |
4 |
16 |
��� ���� ��������� �� ���� ���� ���, ����� �������, ��� �� ����� � ������ ���������. ���� ��� ������������ �� ������ � �� ��� ��������� ����� �����������, ������� ����� ������� ������� � �������������� ������������. �� ������ �������� �� ������, � ���� ����������� ������ ���������� ��� ����� �����������, ����������� �� ����� ��������. ����������, ����� ���������� ����� ��������� ���������� ��� ����������� ���� ������ ����������.
������ ������ ������� ������ �������� ���������� ������ \(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 |
3 |