Упражнения

В этом задании контейнером vector и другими контейнерами из C++, пользоваться нельзя.

A: Мирные ладьи

На шахматной доске размером \(N\times N\) расставлено \(N\) шахматных ладей не бьющих друг друга, то есть на каждой вертикали и каждой горизонтали стоит ровно одна ладья.

Шахматную доску повернули на \(90^\circ\) по часовой стрелке. Выведите получившуюся расстановку ладей.

Первая строка входных данных содержит целое число \(N\), \(1\le N\le 10^5\) — размер доски. Следующие \(N\) строк содержат по одному числу от 1 до \(N\), а именно, в \(i\)-й строке записано число \(a_i\) — номер вертикали, в которой стоит ладья на \(i\)-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до \(N\) сверху вниз, вертикали нумеруются числами от 1 до \(N\) слева направо (см. рисунок).

Программа должна вывести \(N\) чисел — расстановку ладей после поворота в таком же формате.

Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1 при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.

Ввод	Вывод
5 4 2 3 5 1	1 4 3 5 2

B: Сортировка подсчётом

Дана последовательность чисел от 1 до 9. Упорядочите её в порядке возрастания.

Программа получает на вход последовательность чисел. Количество чисел неизвестно, последовательность заканчивается числом 0. Выведите эту же последовательность в порядке возрастания (без числа 0).

Ввод	Вывод
1 2 3 3 2 1 0	1 1 2 2 3 3

C: Плацкартный вагон

В плацкартном вагоне 54 места, пронумерованных числами от 1 до 54. Вагон разбит на 9 купе. Первые 36 мест расположены по левую сторону от прохода, места 1–4 находятся в первом купе, места 5–8 — во втором и т. д. В девятом купе находятся места с номерами 33–36. По правую сторону от прохода находятся боковые места, их номера от 37 до 54, причём они нумеруются в противоположном направлении: места 37 и 38 находятся напротив девятого купе, а места 53 и 54 — напротив первого. Ниже приведена схема всех мест в вагоне.

Для группы школьников нужно купить несколько свободных купе в вагоне. Даны номера свободных мест в поезде. Определите, какое наибольшее число подряд идущих купе полностью свободны.

Программа получает на вход число \(N\) — количество свободных мест в вагоне (\(0 \le N \le 54\)). Следующие \(N\) чисел — номера свободных мест — различные числа от 1 до 54 в произвольном порядке, по одному числу в строке. Программа должна вывести одно целое число — максимальное число подряд идущих свободных купе (купе — места слева от прохода и 2 боковых места) в этом вагоне.

Ввод	Вывод
12 5 6 3 4 8 7 51 9 10 54 49 52	1
1 1	0

D: Черепахи

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: «Впереди меня две черепахи». Другая черепаха говорит: «Позади меня две черепахи». Третья черепаха говорит: «Впереди меня две черепахи и позади меня две черепахи». Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся \(N\) черепах. Каждая черепаха говорит фразу вида: «Впереди меня \(a_i\) черепах, а позади меня \(b_i\) черепах». Ваша задача определить самое большое количество черепах, которые могут говорить правду.

Программа получает на вход целое число \(N\) (\(1\le N\le 100000\)). Далее следуют \(N\) строк, содержащих целые числа \(a_i\) и \(b_i\), по модулю не превосходящие 100000, описывающие высказывание \(i\)-ой черепахи.

Данные о высказываниях черепах приведены в произвольном порядке.

Выведите одно целое число — максимальное количество черепах, которые могут говорить правду.

Решение должно иметь сложность \(O(n)\).

Ввод	Вывод
3 2 0 0 2 2 2	2

E: Кегельбан

\(N\) кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до \(N\). Затем по этому ряду бросили \(K\) шаров, при этом \(i\)-й шар сбил все кегли с номерами от \(l_i\) до \(r_i\) включительно. Определите, какие кегли остались стоять на месте.

Программа получает на вход количество кеглей \(N\) (\(1\le N\le 10^6\)) и количество бросков \(K\) (\(0\le K\le 10^5\)). Далее идет \(K\) пар чисел \(l_i\), \(r_i\), при этом \(1\le l_i\le r_i\le N\).

Программа должна вывести последовательность из \(N\) символов, где \(j\)-й символ есть «I», если \(j\)-я кегля осталась стоять, или «.», если \(j\)-я кегля была сбита. Решение должно иметь сложность \(O(N+K)\).

Ввод	Вывод
10 3 8 10 2 5 3 6	I.....I...

F: Покер

Даны 5 целых чисел, каждое от 1 до 13. Выведите одну из следующих строк:

• если все 5 чисел равны, то выведите "Impossible", иначе
• если равны 4 числа, то вывести "Four of a Kind", иначе
• если одинаковы 3 и 2, то вывести "Full House", иначе
• если одинаковы 3, то вывести "Three of a Kind", иначе
• если одинаковы 2 и 2, то вывести "Two Pairs", иначе
• если одинаковы 2, то вывести "One Pair", иначе
• если есть 5 последовательных, то вывести "Straight", иначе
• вывести "Nothing".

1 3 9 3 2

One Pair

1 5 5 4 4

Two Pairs

1 5 2 4 3

Straight

10 11 12 13 1

Nothing

G: Три части

Дан массив. Его необходимо разбить на три непустые непрерывные части так, чтобы суммы элементов в каждой части были бы равны. Определите количество способов выполнить такое разбиение.

В первой строке входных данных содержится единственное целое число \(n\), \(1\le n\le 10^5\) — количество элементов в массиве (3 ≤ N ≤ 10⁵). В следующих \(n\) строках записаны целые числа \(a_i\) — элементы массива, \(|a_i|\le 10^8\).

Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.

Примеры

6
4
3
-3
5
-1
4

2

3
0
0
0

1

4
3
-2
3
1

0

H: Agar.io

В игре Agar.io по полю передвигаются бактерии разного размера. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом поле одна.

В игре участвуют \(n\) бактерий заданного размера. Определите, какие из них имеют возможность выиграть в этой игре. Программа получает на вход целое число \(n\), \(1\le n\le 10^5\) — количество бактерий. Далее записаны \(n\) чисел \(a_i\) — размеры бактерий, \(1\le a_i\le 10^9\). Числа \(a_i\) заданы в порядке неубывания.

Программа должна вывести \(n\) чисел равных «0» или «1», по одному числу в строке. Если \(i\)-е число равно 0, то это означает, что \(i\)-я бактерия (размер бактерии которого первоначально был равен \(a_i\)) ни при каких обстоятельствах не может выиграть в этой игре. Если \(i\)-е число равно 1, то это означает, что \(i\)-я бактерия имеет возможность выиграть в этой игре.

В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

Ввод	Вывод
4 1 1 3 4	0 0 1 1