Темы
Информатика(2656 задач)
--->
228 задач
<---
Пусть a1 = 2, a2 = 3, an = a1∙a2∙...∙an-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<
Вводится одно натуральное число X, 1 < X ≤ 109.
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
Оценка задачи
1 балл будет набирать программа, верно работающая для X ≤ 100.
6
2 3
5
5
7
0
Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.
Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.
Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.
1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.
Требуется вывести массив после сортировки.
4 1 4 2 3 2 4 3 1 2
1 2 4 3
Вагоны в электричке пронумерованы натуральными числами, начиная с 1 (при этом иногда вагоны нумеруются от «головы» поезда, а иногда – с «хвоста»; это зависит от того, в какую сторону едет электричка). В каждом вагоне написан его номер.
Витя сел в i-й вагон от головы поезда и обнаружил, что его вагон имеет номер j. Он хочет определить, сколько всего вагонов в электричке. Напишите программу, которая будет это делать или сообщать, что без дополнительной информации это сделать невозможно.
На вход программы поступают два числа i и j (1 ≤ i ≤ 1000, 1 ≤ j ≤ 1000), разделенные пробелом.
Выведите одно число — количество вагонов в электричке. Если однозначно определить количество вагонов нельзя, выведите число 0
3 4
6
В обувном магазине продается обувь разного размера. Известно, что одну пару обуви можно надеть на другую, если она хотя бы на три размера больше. В магазин пришел покупатель. Требуется определить, какое наибольшее количество пар обуви сможет предложить ему продавец так, чтобы он смог надеть их все одновременно.
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.
Выведите единственное число — максимальное количество пар обуви.
60 2 60 63
2
26 5 30 35 40 41 42
3
|
+ |
||||
|
+ |
(4,3) |
+ |
||
|
+ |
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 105), а затем сами команды. Команды записаны по одной в строке в следующем формате:
Colori j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).
1 ≤ i ≤ N, 1 ≤ j ≤ M.
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо. Пример ниже некорректен, первое число "3" должно отсутствовать.
Оценка задачи
1 балл получат решения, верно работающие при N ≤ 20, M ≤ 500, K ≤ 1000.
5 5 6 Color 4 2 Neighbors 4 3 Color 2 3 Color 3 3 Neighbors 4 3 Neighbors 5 1
3 4 4 1 4 4 3 3 5 3 4 4 1 4 4 1 3 5 3 2 5 2 4 1