Темы
Информатика(2656 задач)
--->
10 задач
<---
Маленький Вася очень любит уравнения. Однажды ему на глаза попалось уравнение \(x + y + xy = n\). Вася захотел узнать количество пар целых неотрицательных чисел \(x\) и \(y\), которые являются решениями этого уравнения.
Так как Вася еще маленький, то он попросил вас посчитать это количество.
В единственной строке входного файла дано число \(n\) (\(0 \le n \le 10^9\)).
В единственную строку выходного файла выведите ответ на задачу.
Ниже перечислены все решения уравнения \(x + y + xy = 5\)
1. \(x = 0\), \(y = 5\)
2. \(x = 1\), \(y = 2\)
3. \(x = 2\), \(y = 1\)
4. \(x = 5\), \(y = 0\)
5
4
8
3
Воскресенье, утро. Пора на олимпиаду. Вениамин взял пачку чистой бумаги, ручку, пару бутербродов - что еще понадобится? - и открыл картографический сайт чтобы посмотреть, куда и как ему добираться. Какая удача! На пути есть прекрасный парк, а Вениамин как раз любит гулять по паркам. Парк представляет собой прямоугольное поле, разбитое на квадратные клеточки, в каждой из которых либо газон с дорожками, либо какое-то препятствие (заросли кустарника, деревья, а то и вовсе какой-нибудь огороженный памятник).
На олимпиаду нужно прийти вовремя, так что Вениамин не может позволить себе долго разгуливать по парку. Перемещение между двумя соседними по стороне клеточками парка занимает одну секунду. Вениамин не может устоять на месте, поэтому каждую секунду он перемещается в какую-либо соседнюю клеточку. Вениамин решил, что может позволить себе гулять лишние две секунды. Ваша задача: посчитать количество способов пройти через парк так, чтобы время прогулки было ровно на две секунды больше минимального.
Вход в парк и выход из него - это некоторые выделенные различные клетки в парке, выходить за пределы парка запрещается, передвигаться можно только между соседними по ребру клетками. Вениамин должен гулять на две секунды дольше оптимального времени прохода от входа к выходу, поэтому он может в качестве промежуточной точки пути оказаться на входе или выходе. Поскольку ответ на задачу может быть довольно большим, от вас требуется остаток от деления количества путей на \(10^9 + 9\).
В первой строке входного файла заданы два числа \(h\) и \(w\): размеры парка. Следующие \(h\)~строк содержат по \(w\) символов в каждой. Символ "." означает, что в соответствующей клетке дорожка или газон, по которому можно ходить. Символ "#" означает препятствие. Символы "E" и "X" означают вход в парк и выход из него соответственно.
Ограничения: \(1 \le h \le 500\), \(1 \le w \le 500\), символы "E" и "X" встречаются во входном файле ровно по одному разу. Обратите внимание, что вход и выход не обязательно находятся на границе парка: например, клеткой входа может быть расположенный в парке вестибюль метро, из которого Вениамин собирается выходить на своем пути.
В выходной файл выведите одно число: количество путей, которые длиннее кратчайшего ровно на две секунды. Если парк устроен так, что невозможно добраться от входа до выхода, то выведите ноль.
6 9 ......... ..######X ..#...... .E..####. ..##...#. .....#...
15
Вася очень любит изучать разные интересные классы чисел. Сегодня он изучает палиндромные числа.
Вася называет число палиндромным, если оно записывается одинаково слева направо и справа налево. При этом, Вася разрешает приписывать к числу несколько (возможно ни одного) лидирующих нулей. Например, числа 22, 4554, 12321, 5050 являются палиндромными. В частности, к числу 5050 необходимо приписать один ноль, чтобы получить 05050, которое читается одинаково слева направо и справа налево.
В числе прочих, Васю интересуют палиндромные числа, отличающиеся на 2. Для их исследования Вася рассматривает такие \(x\), что \(x-1\) и \(x+1\) являются палиндромными. Такие числа Вася называет междупалиндромными. Вася хочет найти количество междупалиндромных чисел \(x\) от \(L_k\) до \(R_k\) включительно для нескольких отрезков \([L_k, R_k]\).
Помогите Васе в этом нелегком деле!
Входной файл содержит несколько отрезков, которые интересуют Васю. В первой строке задано одно число \(T\) (\(1 \le T \le 2\,000\)) - количество отрезков. В каждой из следующих \(T\) строк заданы два числа \(L_{k}\) и \(R_{k}\) (\(1 \le L_{k} \le R_{k} \le 10^{18}\)) - границы отрезка.
Выведите \(T\) строк. В \(k\)-ой строке выведите одно число - количество междупалиндромных чисел в отрезке от \(L_{k}\) до \(R_{k}\) включительно.
От 17 до 24 палинромными являются числа 20 и 22. Поэтому единственное междупалиндромное число на отрезке \([18, 23]\) - это 21. Во втором примере, число 21 опять подходит. От 49 до 56 палинромными являются числа 50, 55. Междупалиндромных чисел на отрезке \([50, 55]\) нет.
3 18 23 21 21 50 55
1 1 0
Недавно на выставку странных устройств привезли новый экспонат. Его суть заключается в том, что он может генерировать случайную перестановку из чисел от \(1\) до \(n\), после чего сканировать ее и выводить на экран \(n - k + 1\) чисел, \(i\)-е из этих чисел обозначает количество инверсий на отрезке с \(i\) по \(i + k - 1\) сгенерированной перестановки.
Напомним, что инверсией в перестановке \(p\) называется всякая пара индексов \(i, j\) такая, что \(1 \le i < j \le n\) и \(p[i] > p[j]\).
У этого экспоната кроме экрана есть две ручки - первая определяет \(n\), то есть длину перестановки, а вторая определяет \(k\). Посетитель Вася повернул ручки и увидел на экране числа. Теперь он хочет понять, какую перестановку сгенерировало это странное устройство. Помогите ему в этом.
В первой строке содержатся два натуральных числа \(n\) и \(k\) (\(2 \le n \le 10^5\), \(2 \le k \le 5\), \(n \ge k\)). Во второй строке даны \(n - k + 1\) чисел, выведенные на экран устройством. Гарантируется, что устройство исправно, и существует хотя бы одна перестановка, по которой можно сгенерировать эти числа.
Выведите \(n\) чисел, разделенных пробелами - cгенерированную устройством перестановку. Если возможных перестановок несколько, то выведите любую.
3 2 0 1
2 3 1
Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.
Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник \(n \times m\), составленный из разноцветных квадратов \(1 \times 1\). После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.
Казимир решил исправить картину следующим образом. Он может взять строку своей картины, более половины единичных квадратов в которой покрашено в один и тот же цвет, и перекрасить всю строку в этот цвет. Аналогично он может перекрасить столбец, более половины единичных квадратов в котором покрашено в один цвет.
Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.
В первой строке заданы два числа \(n\) и \(m\) (\(1 \le n, m \le 300\)) - размеры картины. Далее, в \(n\)~строках задано по \(m\) чисел \(c_{i,j}\) (\(1 \le c_{i,j} \le 1\,000\,000\)) - цвета квадратов, из которых составлена картина. Гарантируется, что на картине представлено хотя бы два цвета.
Если Казимиру не удастся сделать картину достаточно простой, выведите "Poor Kazimir".
Иначе, выведите в первой строке \(k\) - количество действий, которое нужно сделать Казимиру. Действия могут быть двух видов:
Разрешается сделать не более 1000 действий.
3 3 1 1 2 2 1 1 2 2 2
5 R 1 R 2 C 1 C 2 C 3
3 3 1 1 2 2 1 1 2 2 2
5 R 1 R 2 C 1 C 2 C 3
2 2 1 2 3 4
Poor Kazimir