Реализуйте равномерный генератор псевдослучайных пар целых чисел ($$$a$$$, $$$b$$$), таких что $$$1 \le a \le b \le k$$$. Пояснение: при каждом обращении к генератору любая допустимая пара должна порождаться с одинаковой вероятностью.
В первой строке входных данных вводится целое число $$$k$$$ ($$$2 \le k \le 10^9$$$).
Во второй строке вводится целое число $$$n$$$ — количество пар, которое нужно сгенерировать ($$$1 \le n \le 10000$$$).
Используя созданный генератор, получите и выведите $$$n$$$ пар. Каждая пара выводится в отдельной строке через пробел.
53
1 4 3 5 2 2
При тестировании решений будет проверяться принадлежность выборки из ответа равномерному закону распределения на интервале допустимых значений. Никаких других проверок качества генератора выполняться не будет.
На шахматной доске размером $$$n$$$ x $$$n$$$ стоит слон. За один ход слон может переместиться на любое число клеток по диагонали.
Определите количество возможных путей слона из клетки ($$$x_1$$$, $$$y_1$$$) в клетку ($$$x_2$$$, $$$y_2$$$) с наименьшим числом ходов.
В первой строке входных данных вводится целое число $$$n$$$ — размер поля ($$$1 \le n \le 10^{9}$$$).
Во второй строке входных данных вводятся два целых числа $$$x_1$$$ и $$$y_1$$$, в третьей строке — два целых числа $$$x_2$$$ и $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n$$$).
Выведите одно целое число — количество различных путей, содержащих наименьшее число ходов.
53 24 5
2
Иллюстрация к примеру из условия:
Правильной скобочной последовательностью (ПСП) назовём строку, состоящую только из круглых скобок, где каждой закрывающей скобке найдётся соответствующая открывающая, и наоборот.
Примеры ПСП: '()', '(())', '()(())'. Примеры строк, не являющихся ПСП: '())', ')(', '(()'.
Более строгое определение ПСП звучит так:
Напишите программу для подсчёта количества таких ПСП длины $$$2n$$$, которые по-прежнему останутся ПСП, если в них убрать две центральные скобки (то есть скобки с номерами $$$n$$$ и $$$n+1$$$). Например, при $$$n$$$=3 ответ равен 3 — это строки '((()))', '()()()' и '(()())'.
Вводится одно целое число $$$n$$$ ($$$1 \le n \le 30$$$).
Выведите одно целое число — количество искомых ПСП.
3
3
Технология виртуальной памяти позволяет выполнять программы, требующие больше оперативной памяти, чем установлено в компьютере. В большинстве современных архитектур виртуальная память организуется с помощью страничной адресации. Рассмотрим упрощённо данную технологию.
Вся виртуальная память разделена на страницы — области памяти фиксированной длины. Когда программа обращается к какому-то адресу, то по адресу вычисляется номер страницы и проверяется, содержится ли данная страница в физической памяти либо выгружена на диск.
Если нужная страница выгружена на диск, то её нужно переместить в физическую память. Но, поскольку она занята другими страницами, сначала нужно какую-то страницу переместить из физической памяти на диск. Чтобы определить номер выгружаемой страницы, используется метод LRU (least recently used): на диск будет перемещена та страница, к которой дольше всего не было обращений. Если же таких страниц несколько, пусть это будет страница с наименьшим номером среди них.
Ваша задача — смоделировать работу описанной системы.
В первой строке вводится целое число $$$n$$$ — размер виртуальной памяти в страницах ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке вводится целое число $$$m$$$ — размер физической памяти в страницах ($$$1 \le m \le n$$$).
В третьей строке вводится целое число $$$k$$$ — количество обращений к страницам ($$$1 \le k \le 2 \cdot 10^5$$$).
В четвёртой строке вводятся $$$k$$$ целых чисел от $$$1$$$ до $$$n$$$ — номера страниц в порядке обращения к ним.
Перед началом работы программы в физической памяти находятся страницы с номерами от 1 до $$$m$$$, а на диске — страницы с номерами от $$$m+1$$$ до $$$n$$$.
Выведите в порядке возрастания $$$m$$$ целых чисел — номера страниц, находящихся в физической памяти по окончании работы программы.
3221 3
1 3
Условие этой задачи очень простое: найдите последнюю ненулевую цифру в числе $$$1^1 \cdot 2^2 \cdot 3^3 ... \cdot n^n$$$.
Вводится одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).
Выведите одно целое число от 1 до 9.
5
4
На заводе имеется $$$N-1$$$ цех по производству различных деталей. Каждый цех имеет ровно один выходящий конвейер, на котором пересылаются детали из него в какой-то другой цех. При этом каждый цех способен также принимать (и затем отправлять по своему выходящему конвейеру) любое количество деталей, пересылаемых какими-то другими цехами к нему.
И вот приближается время сборки! Недавно на заводе открыли ещё один цех с номером $$$N$$$ для финальной сборки изделий. Теперь требуется построить один или несколько дополнительных конвейеров так, чтобы любая деталь в конечном итоге смогла попасть в цех $$$N$$$.
Строить конвейеры – дело затратное. Для каждого цеха известна стоимость строительства одного дополнительного конвейера, выходящего из него (заметим, что пункт назначения на стоимость не влияет). Определите минимальную сумму, необходимую для строительства новых конвейеров, а также какие именно конвейеры следует построить. Строить несколько дополнительных конвейеров для любого из $$$N$$$ цехов не запрещается.
В первой строке входных данных задаётся целое число $$$N$$$ ($$$3 \le N \le 2 \cdot 10^5$$$).
Во второй строке содержится $$${N-1}$$$ натуральное число $$$e_1$$$, $$$e_2$$$, $$$\dots$$$, $$$e_{N-1}$$$ ($$$e_i \le {N-1}$$$) — номера цехов, куда приходят конвейеры, выходящие из цехов с номерами $$$1$$$, $$$2$$$, $$$\dots$$$, $$${N-1}$$$ соответственно.
В третьей строке содержится $$$N$$$ целых чисел $$$c_1$$$, $$$c_2$$$, $$$\dots$$$, $$$c_N$$$ ($$$1 \le c_i \le 10^9$$$) — стоимость постройки одного дополнительного конвейера, пересылающего детали из цеха с номером $$$1, 2, \dots, N$$$ соответственно.
В первой строке выходных данных выведите два числа $$$S$$$ и $$$K$$$ — суммарную стоимость постройки новых конвейеров и их количество.
Далее выведите $$$K$$$ строк, содержащих два натуральных числа $$$a_j$$$ и $$$b_j$$$, где $$$a_j$$$ — номер цеха, откуда выходит $$$j$$$-й новый конвейер, а $$$b_j$$$ — номер цеха, куда он приходит.
Если есть несколько правильных ответов, выведите любой.
42 3 114 13 12 11
12 1 3 4
52 1 4 31 1 1 1 1
2 2 2 3 4 5
Иллюстрация к первому примеру:
Скромный мальчик Миша называет натуральное число скромным, если оно содержит ровно 7 натуральных делителей. Помогите Мише найти количество скромных чисел в интервале от $$$a$$$ до $$$b$$$ включительно.
Вводятся два целых числа $$$a$$$ и $$$b$$$, каждое в отдельной строке ($$$1 \le a \le b \le 10^{18}$$$).
Выведите одно целое число — количество скромных чисел в интервале от $$$a$$$ до $$$b$$$.
50100
1
В примере в интервале от 50 до 100 имеется всего одно скромное число — это число 64.
Одним из показателей научной продуктивности учёных является индекс Хирша. Индекс Хирша учёного равен $$$H$$$, если им опубликовано хотя бы $$$H$$$ научных работ, на каждую из которых есть не менее $$$H$$$ ссылок (но при этом не набирается $$$H+1$$$ работ с $$$H+1$$$ ссылками). Например, если учёный опубликовал 4 работы, на которые имеются 7, 4, 5 и 2 ссылки соответственно, то его индекс Хирша равен 3.
Научному работнику Ивану Ивановичу для получения гранта нужно поднять свой индекс Хирша до величины хотя бы $$$H$$$. Для этого Иван Иванович договорился с коллегами, что при публикации своих статей они будут вставлять ссылки на его работы, но не более чем по две ссылки в каждой статье. Заметим, что в статье не может быть двух одинаковых ссылок.
Определите, какое наименьшее количество новых статей должны опубликовать коллеги Ивана Ивановича, чтобы его индекс Хирша поднялся до $$$H$$$.
В первой строке входных данных записано целое число $$$N$$$ — количество статей у Ивана Ивановича ($$$1 \le N \le 10^5$$$).
В следующей строке записаны целые числа $$$L_1$$$, $$$L_2$$$, ..., $$$L_N$$$ — текущее количество ссылок на каждую статью ($$$0 \le L_i \le 10^9$$$).
В последней строке записано целое число $$$H$$$ ($$$1 \le H \le N$$$) — требуемый индекс Хирша.
Выведите одно целое число — наименьшее количество новых статей, которое должны опубликовать коллеги Ивана Ивановича.
4 7 4 5 2 4
2
3 1 1 2 2
1
Дано множество точек на плоскости. Найдите выпуклый многоугольник наименьшей площади, содержащий все эти точки.
Требуется получить два варианта ответа. В первом варианте вам нужно отобрать только те точки, которые окажутся в вершинах искомого многоугольника. Во втором варианте вам нужно отобрать все точки, которые окажутся на границе искомого многоугольника — и в вершинах, и на сторонах.
В первой строке входных данных записано целое число $$$n$$$ — количество точек ($$$3 \le n \le 10^5$$$).
В каждой из следующих $$$n$$$ строк записано по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты очередной точки ($$$-10^9 \le x_i, y_i \le 10^9$$$).
Гарантируется, что никакие две точки не совпадают и существуют три точки, не лежащие на одной прямой.
В первой строке ответа выведите целое число $$$n_1$$$ — количество точек в вершинах многоугольника.
В каждой из следующих $$$n_1$$$ строк выведите пару целых чисел — координаты очередной точки в порядке обхода против часовой стрелки. Первой должна идти самая нижняя точка, а если таких несколько, то самая левая из них.
В следующей строке выведите целое число $$$n_2$$$ — количество точек в вершинах и на сторонах многоугольника.
В каждой из следующих $$$n_2$$$ строк выведите пару целых чисел — координаты очередной точки в порядке обхода против часовой стрелки. Аналогично, первой должна идти самая нижняя точка, а если таких несколько, то самая левая из них.
61 13 51 47 33 34 2
4 1 1 7 3 3 5 1 4 5 1 1 4 2 7 3 3 5 1 4
Иллюстрация к примеру из условия:
В куче лежат $$$N$$$ камней. Два игрока по очереди делают ходы. На каждом ходе игрок может взять от $$$1$$$ до $$$K$$$ камней, но не может брать столько, сколько взял его соперник на предыдущем ходе. Тот, кто не сможет сделать ход, проигрывает. Определите, кто выиграет, если оба игрока действуют оптимально.
В первой строке входных данных вводится целое число $$$T$$$ — количество партий игры ($$$1 \le T \le 10$$$). В следующих $$$T$$$ строках вводятся по два целых числа $$$N_i$$$ и $$$K_i$$$ ($$$2 \le N_i \le 5000$$$, $$$2 \le K_i \le N_i$$$).
Для каждой партии выведите в отдельной строке 1, если выиграет первый игрок, и 2, если второй.
2 4 2 4 3
1 2
В примере при $$$N=4$$$, $$$K=2$$$ выиграет первый игрок. Он возьмёт один камень. Теперь у его соперника есть единственный ход — взять два камня, и затем первый игрок заберёт оставшийся камень.
При $$$N=4$$$, $$$K=3$$$ выиграет второй игрок. Если первый игрок возьмёт 1 или 3 камня, то второй возьмёт оставшиеся 3 или 1. Если же первый игрок возьмёт 2 камня, то второй возьмёт 1, и первому будет некуда ходить.
Данная версия задачи отличается от предыдущей только ограничением на $$$N$$$.
В куче лежат $$$N$$$ камней. Два игрока по очереди делают ходы. На каждом ходе игрок может взять от $$$1$$$ до $$$K$$$ камней, но не может брать столько, сколько взял его соперник на предыдущем ходе. Тот, кто не сможет сделать ход, проигрывает. Определите, кто выиграет, если оба игрока действуют оптимально.
В первой строке входных данных вводится целое число $$$T$$$ — количество партий игры ($$$1 \le T \le 10$$$). В следующих $$$T$$$ строках вводятся по два целых числа $$$N_i$$$ и $$$K_i$$$ ($$$2 \le N_i \le 10^6$$$, $$$2 \le K_i \le N_i$$$).
Для каждой партии выведите в отдельной строке 1, если выиграет первый игрок, и 2, если второй.
2 4 2 4 3
1 2
В примере при $$$N=4$$$, $$$K=2$$$ выиграет первый игрок. Он возьмёт один камень. Теперь у его соперника есть единственный ход — взять два камня, и затем первый игрок заберёт оставшийся камень.
При $$$N=4$$$, $$$K=3$$$ выиграет второй игрок. Если первый игрок возьмёт 1 или 3 камня, то второй возьмёт оставшиеся 3 или 1. Если же первый игрок возьмёт 2 камня, то второй возьмёт 1, и первому будет некуда ходить.
Проверьте правильность арифметического равенства, которое может содержать только десятичные цифры и знаки '+' и '-' (унарные и бинарные). Равенство должно содержать ровно один знак '='. Неравенство не должно содержать других символов, в том числе пробелов. Ведущие нули в числах разрешены. Унарные операции могут использоваться несколько раз подряд.
Примеры верных, неверных и некорректно записанных равенств:
Первая строка ввода содержит равенство (не более $$$3 \cdot 10^6$$$ символов с ASCII-кодами от 32 до 127 включительно). Строка завершается переводом строки.
Выведите 'YES', если равенство верно, 'NO', если оно неверно, и 'ERROR', если запись равенства некорректна.
-5+10+3=2+6
YES
2+2=5
NO
2*2=4
ERROR