На шахматной доске размером \(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 |
Дана последовательность чисел от 1 до 9. Упорядочите её в порядке неубывания.
Программа получает на вход последовательность чисел. Количество чисел неизвестно, последовательность заканчивается числом 0. Выведите эту же последовательность в порядке возрастания (без числа 0).
| Ввод | Вывод |
|---|---|
1 2 3 3 2 1 0 |
1 1 2 2 3 3 |
В плацкартном вагоне 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 |
Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: «Впереди меня две черепахи». Другая черепаха говорит: «Позади меня две черепахи». Третья черепаха говорит: «Впереди меня две черепахи и позади меня две черепахи». Как такое может быть? Ответ: третья черепаха врет!
По дороге одна за другой движутся \(n\) черепах. Каждая черепаха говорит фразу вида: «Впереди меня \(a_i\) черепах, а позади меня \(b_i\) черепах». Ваша задача определить самое большое количество черепах, которые могут говорить правду.
Решение должно иметь сложность \(O(n)\).
Программа получает на вход целое число \(n\) (\(1\le n\le 100000\)). Далее следуют \(n\) строк, содержащих целые числа \(a_i\) и \(b_i\), по модулю не превосходящие 100000, описывающие высказывание \(i\)-ой черепахи.
Данные о высказываниях черепах приведены в произвольном порядке.
Выведите одно целое число — максимальное количество черепах, которые могут говорить правду.
| Ввод | Вывод |
|---|---|
3 2 0 0 2 2 2 |
2 |
\(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... |
Даны 5 целых чисел, каждое от 1 до 13. Выведите одну из следующих строк:
| Ввод | Вывод |
|---|---|
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 |
Дан массив. Его необходимо разбить на три непустые непрерывные части так, чтобы суммы элементов в каждой части были бы равны. Определите количество способов выполнить такое разбиение.
В первой строке входных данных содержится единственное целое число \(n\) — количество элементов в массиве (\(3\le n \le 10^5\)). В следующих \(n\) строках записаны целые числа \(a_i\) — элементы массива, \(|a_i|\le 10^8\).
Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.
В первом примере можно получить два разбиения: [4], [3, −3, 5, −1], [4] и [4, 3, −3], [5, −1], [4].
Во втором примере имеется единственное возможное разбиение [0], [0], [0], потому что в каждой записи должно быть хотя бы одно число.
В третьем примере выполнить подходящее разбиение невозможно.
| Ввод | Вывод |
|---|---|
6 4 3 -3 5 -1 4 |
2 |
3 0 0 0 |
1 |
4 3 -2 3 1 |
0 |
В игре 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 |