Несколько геометрических фигур расположены в ряд. Среди них два треугольника, а остальные — квадраты. Известно, что справа от первого треугольника находится второй треугольник и $$$a$$$ квадратов, а слева от второго треугольника — первый треугольник и $$$b$$$ квадратов. Определите минимальное и максимальное количество фигур, при котором такая ситуация возможна.
Вводятся два целых числа $$$a$$$ и $$$b$$$, каждое в отдельной строке ($$$0 \le a, b \le 10^9$$$).
Выведите два целых числа — минимальное и максимальное количество фигур.
23
5 7
Определите, сколькими способами натуральные числа от $$$1$$$ до $$$2n$$$ можно разбить на $$$n$$$ пар так, чтобы в каждой паре второе число хотя бы в два раза превышало первое.
Единственная строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 25$$$).
Выведите одно целое число — ответ.
3
2
В примере можно составить два варианта пар: 1 – 5, 2 – 4, 3 – 6 и 1 – 4, 2 – 5, 3 – 6.
Дан набор из $$$n$$$ целых чисел. Определить, какое наименьшее количество целых чисел нужно добавить к этому набору, чтобы все числа можно было выстроить в арифметическую прогрессию.
Пояснение: последовательность чисел образует арифметическую прогрессию, если все разности между парами соседних элементов одинаковы.
В первой строке записано целое число $$$n$$$ — количество чисел ($$$1 \le n \le 10^5$$$). В следующих $$$n$$$ строках записаны целые числа $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
Выведите одно целое число — минимальное количество целых чисел, которое нужно добавить ко входному набору. Если решений нет, выведите -1.
3-271
1
В примере можно добавить одно число 4, тогда последовательность -2 1 4 7 образует арифметическую прогрессию.
Кодовый замок содержит несколько дисков. На каждом диске написаны последовательно цифры от 0 до 9 (после 9 идёт снова 0).
За одно действие можно ухватить пальцами один или сразу два соседних диска и повернуть их вместе на произвольный угол. Определите минимальное количество таких действий для открытия замка.
В первой строке входных данных записан начальный код на замке. Во второй строке записан код открытия замка. Длины строк одинаковы и не превосходят $$$10^5$$$.
Выведите одно целое число — минимальное количество действий для открытия замка.
00007329
3
В примере можно действовать так. Вращаем первый (верхний) диск, чтобы получить код 7000. Затем вращаем одновременно второй и третий диск, чтобы получить код 7330. Наконец, вращаем одновременно последние два диска, чтобы получить код 7329. Итого 3 действия.
В ряд выстроены $$$n$$$ шариков. Каждый шарик покрашен в один из трёх возможных цветов. За одно действие можно поменять местами два любых шарика.
Определите, какое наименьшее количество таких обменов потребуется, чтобы в результате все шарики одного цвета стояли подряд. Другими словами, не должно быть двух шариков одинакового цвета, между которыми есть шарики другого цвета.
В первой строке входных данных записано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке записаны $$$n$$$ целых чисел в диапазоне от $$$1$$$ до $$$3$$$ — цвета шариков.
Выведите одно целое число — минимальное количество обменов.
52 1 2 2 1
1
В ряд выстроены $$$n$$$ шариков. Каждый шарик покрашен в один из десяти возможных цветов. За одно действие можно поменять местами два соседних шарика.
Определите, какое наименьшее количество таких обменов потребуется, чтобы в результате все шарики одного цвета стояли подряд. Другими словами, не должно быть двух шариков одинакового цвета, между которыми есть шарики другого цвета.
В первой строке входных данных записано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Во второй строке записаны $$$n$$$ целых чисел в диапазоне от $$$1$$$ до $$$10$$$ — цвета шариков.
Выведите одно целое число — минимальное количество обменов.
42 1 2 1
1
Это задача с двойным запуском.
На лабораторной работе по физике студенты разработали устройство, позволяющее передавать текстовые сообщения из строчных латинских букв с помощью лазера. Перед отправкой сообщение переводится в двоичный код и затем передаётся последовательно бит за битом.
Однако, при тестировании устройства выявилась проблема. Оказалось, что если при передаче встретятся четыре одинаковых бита подряд (то есть «0000» или «1111»), то на приёмной стороне сбивается синхронизация. Поэтому необходимо придумать способ кодирования, при котором такая ситуация будет невозможна. Также разработчики хотят, чтобы количество битов в закодированном сообщении превышало длину исходного сообщения не более чем в шесть раз.
Разработайте какой-нибудь способ кодирования и декодирования, удовлетворяющий данным требованиям.
Первая строка входных данных содержит число $$$t$$$, равное 1 или 2.
Если $$$t=1$$$, то вторая входная строка содержит сообщение, которое нужно закодировать. Оно состоит из строчных латинских букв и имеет длину от 1 до 10000 символов.
Если $$$t=2$$$, то вторая входная строка содержит закодированное ранее вашей программой сообщение, которое требуется декодировать.
Выведите одну строку — закодированное либо декодированное сообщение.
1
aba
100101101101100101
2
100101101101100101
aba
Это интерактивная задача.
Игровое поле представляет собой полоску толщиной в одну клетку и длиной $$$n$$$ клеток . Два игрока по очереди делают ходы. На каждом ходу выбирается пустая клетка, и в неё ставится крестик. При этом нельзя, чтобы на поле оказывалось больше двух крестиков подряд. Проигрывает игрок, которому некуда сделать ход.
Напишите программу, играющую против программы жюри. Ваша программа должна выиграть все раунды. Это всегда возможно, поскольку вы сами выбираете, кто делает первый ход.
Вначале прочитайте целое число $$$n$$$ ($$$1 \le n \le 30$$$) — длину полоски.
Далее решите, кто будет делать первый ход. Выведите 1, если вы ходите первым, иначе выведите 2. Затем выведите перевод строки и выполните сброс буфера в стандартный поток.
Далее ваша программа должна в цикле делать следующее.
Пример ввода-вывода:
| Ввод | Вывод |
| 4 | |
| 1 | |
| 4 | |
| 2 | |
| 1 | |
| 0 |
Для сброса буфера используйте:
Рассмотрим квадратную матрицу $$$a$$$ размера $$$n$$$, состоящую только из нулей и единиц.
Выполним над ней следующий алгоритм: пока существуют такие индексы $$$i$$$, $$$j$$$, $$$k$$$ (не обязательно различные), что $$$a[i][j]=1$$$, $$$a[j][k]=1$$$, $$$a[i][k]=0$$$, заменяем $$$a[i][k]$$$ на $$$1$$$. Получившуюся в итоге матрицу назовём транзитивным замыканием матрицы $$$a$$$.
Для заданной матрицы $$$a$$$ найдите такую матрицу $$$b$$$, что она содержит минимальное количество единиц, а её транзитивное замыкание совпадает с транзитивным замыканием матрицы $$$a$$$.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$).
В следующих $$$n$$$ строках записаны по $$$n$$$ чисел 0 или 1 — элементы матрицы $$$a$$$.
Выведите искомую матрицу $$$b$$$. Если есть несколько верных ответов, выведите любой.
31 1 11 0 10 0 1
0 1 0 1 0 1 0 0 1
Матрицы из примера имеют следующее транзитивное замыкание:
1 1 1
1 1 1
0 0 1
На открытии олимпиады каждому участнику выдали ручку и блокнот. Поскольку из-за «оптимизации» бюджета приобрести другие призы не получилось, жюри приняло решение на закрытии олимпиады вручить каждому призёру ещё $$$a$$$ ручек и $$$b$$$ блокнотов, а каждому победителю — $$$2a$$$ ручек и $$$2b$$$ блокнотов.
Определите, какое минимальное количество человек могло участвовать в олимпиаде, если всего было выдано $$$c$$$ ручек и $$$d$$$ блокнотов.
Пояснение: множества победителей и призёров не пересекаются.
Входные данных содержат четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$1 \le a, b, c, d \le 10^{18}$$$), каждое число в отдельной строке.
Выведите одно целое число — наименьшее возможное количество участников. Если решения нет, выведите 0.
231012
6
2312
0
В первом примере среди 6 участников было либо ноль победителей и два призёра, либо один победитель и ноль призёров.