Страница: 1 2 >> Отображать по:
#36
Псевдопростые числа
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Пусть 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
#37
\"Сортировка\" с конфеткой
  

Дан массив из 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
#39
Обувной магазин
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Входные данные

Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

Выходные данные

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

Примеры
Входные данные
60
2
60 63
Выходные данные
2
Входные данные
26 
5
30 35 40 41 42
Выходные данные
3
#41
Быстрые шахматы
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

На шахматной доске (размером 8 Х 8 клеток) расставлены фигуры. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти последовательность ходов, после которой на доске останется одна фигура.<

Ладья ходит по горизонтали или вертикали на любое число клеток. Слон ходит по диагонали на любое число клеток. Ферзь ходит по горизонтали, вертикали или диагонали на любое число клеток. Эти фигуры не могут перепрыгивать через другие фигуры. Конь ходит на две клетки по горизонтали или вертикали и на одну клетку в перпендикулярном направлении (например, на 2 клетки вверх и на одну клетку вправо и т.п.), при этом он может перепрыгивать через другие фигуры.

Входные данные

В восьми строках входных данных записаны по 8 символов, описывающих шахматную доску: R — ладья, B — слон, K — конь, Q — ферзь, точка обозначает пустую клетку. На доске изначально стоит не менее двух и не более десяти фигур.

Выходные данные

Выведите возможную последовательность в следующем формате. Для каждого хода указывается сначала клетка, с которой делается ход, затем двоеточие, затем клетка, на которую делается ход. Клетка задается столбцом и строкой: столбцы нумеруются слева направо строчными латинскими буквами a, b, c, d, e, f, g, h; строки — снизу вверх цифрами 1, 2, 3, 4, 5, 6, 7, 8.

Если решений несколько, приведите любое из них. Если решений нет, выведите NO SOLUTION

Примеры
Входные данные
........
........
.B......
........
........
....K...
........
........
Выходные данные
b6:e3
Входные данные
..K.....
..K.....
BR......
.B......
........
........
........
........
Выходные данные
c7:a6
b6:a6
b5:a6
a6:c8
#42
Красно-синий граф
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано N точек. Из каждой точки исходят красные или синие ребра во все точки с большим номером. Требуется определить, существует ли пара точек такая, что из первой можно добраться до второй как по красным ребрам так и по синим.

Даны N точек, занумерованных числами 1, 2, ..., N. От каждой точки с меньшим номером к каждой точке с большим номером ведет стрелка красного или синего цвета. Раскраска стрелок называется однотонной, если нет двух таких точек A и B, что от A до B можно добраться как только по красным стрелкам, так и только по синим.

Ваша задача — по заданной раскраске определить, является ли она однотонной.

Входные данные

В первой строке входных данных содержится единственное число N (3 ≤ N ≤ 5000).

В следующих N–1 строках идет описание раскраски. В (i+1)-й строке  записано (N–i) символов R (красный) или B (синий), соответствующих цвету стрелок, выходящих из точки i и входящих в точки (i+1), (i+2), ..., N соответственно.

Выходные данные

Выведите YES, если приведенная раскраска является однотонной, и NO в противном случае.

Оценка задачи

1 балл будут набирать решения, верно работающие для N ≤ 50.

Примеры
Входные данные
3
RB
R
Выходные данные
NO
Входные данные
3
RR
R
Выходные данные
YES
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест