Один мальчик Флор придумал задачку, и даже решение!!! Однако его решение не очень умное, и не работает, если в числе есть хотя бы один 0. Так как число в тесте может быть очень большое, Флор просит вас помочь ему заменить тесты, то есть вывести минимально возможное число без 0, больше оригинального, либо равное оригинальному, чтобы его решение работало на всех тестах.
В единственной строке дано число $$$n$$$ ($$$0 \le n \le 10^{5000}$$$)*
*длина числа $$$n$$$ не превосходит $$$5000$$$
Вывести одно целое число, минимально возможное число без нулей, больше либо равное оригинальному
Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.
12345067089
12345111111
Любимая игра Флюра «EG 2» наконец-то вышла! Но у него возникла проблема: на его компьютере почти не осталось свободного места, и теперь он боится, что не сможет её скачать.
Известно, что файлы игры можно представить в виде строки из чисел от $$$0$$$ до $$$n$$$ включительно, записанных подряд в двоичном виде, и Флюру нужно узнать длину этой строки.
К примеру, для $$$n = 3$$$ файлы игры будут представлять собой $$$011011$$$, так как $$$0 = 0_2$$$, $$$1 = 1_2$$$, $$$2 = 10_2$$$ и $$$3 = 11_2$$$.
В единственной строке дано число $$$n$$$ $$$(1 \le n \le 10^5)$$$.
Выведите длину файла.
Всего в задаче $$$10$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 10 баллов.
3
6
В $$$2033$$$ году группа пылесосов под управлением ChatGPT захватила мир. Теперь люди выполняют их работу и чистят полы в их домах.
Дом представляет собой матрицу n на m, где символ «.» означает, что пол чист, а «*», что пол грязный.
К счастью захват мира привнес нечто новое — появилась волшебная квадратная тряпка со стороной длины $$$k$$$, с помощью неё за 1 секунду очистить любой полностью загрязненный квадрат размера $$$\textbf{строго} $$$ $$$k$$$ на $$$k$$$.
Роботы-пылесосы не любят ждать, поэтому необходимо выполнить работу за кратчайшее время.
В первой строке записаны три целых числа $$$n,m,k$$$ $$$(1 \le n,m,k \le 10^5, 1 \le n \cdot m \le 10^5)$$$ — размеры дома и тряпки
Далее следуют $$$n$$$ строк по $$$m$$$ символов — загрязненность клеток дома
Выведите одно целое число — ответ на задачу, если очистить дом полностью невозможно выведите -1
Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.
4 4 2**..**....**..**
2
4 4 2**..*.....**..**
-1
Сегодня на уроке информатики Шамилю стало скучно, и он решил порисовать на клетчатой бумаге. На первом шаге он закрасил какую-то клетку чёрным, а затем следовал алгоритму: если на предыдущем шаге клетки были закрашены черным цветом, то он закрашивает все соседние с ними по стороне клетки, которые ещё не закрашены, в белый, а иначе соседние раскрашивались в чёрный.
На картинке ниже изображён листок Шамиля после трёх шагов. Номер на каждой клетке – это шаг, на котором он появился.
Дано число $$$n$$$ $$$(1 \le n \le 10^9)$$$.
Выведите количество чёрных клеток на листке после $$$n$$$ шагов.
Всего в задаче $$$10$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 10 баллов.
1
1
3
9
4
9
Вадим гулял по Бразильскому лесу и наткнулся на дикое племя, которое, конечно же, взяло его в плен. Чтобы выбраться из плена, Вадиму необходима палка длиной минимум $$$x$$$, с помощью которой можно достать до рычага, открывающего дверь. К счастью, на полу лежало $$$n$$$ палок, каждая длиной $$$a_i$$$, а также Вадим находился на заочном обучении в Хогвартсе и знает 2 заклинания:
- выбрать одну из палок и увеличить её длину на $$$b$$$.
- выбрать одну из палок и увеличить её длину в $$$2$$$ раза.
В первой строке ввода даны 4 целых числа $$$n$$$ $$$(1 \le n \le 10^5)$$$ и $$$b,x,k$$$ $$$(1 \le b,x,k \le 10^9)$$$ — количество палок на полу и параметры $$$b,x,k$$$ соответственно.
Во второй строке ввода даны $$$n$$$ чисел $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — длины палок.
Выведите YES, если Вадим сможет выбраться из плена, или NO, если у него не получится.
Всего в задаче $$$50$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 2 балла.
5 1 8 21 2 1 1 2
YES
5 5 9 11 3 4 2 3
YES
5 5 10 11 2 4 3 1
NO
Самат участвует в олимпиаде по математике. Однако в этом году много школьников набрали одинаковый балл, и жюри пришлось их как-то разделять. Они придумали такую игру: всего есть $$$n$$$ жюри, каждый из них загадывает одно число $$$a_i$$$, дальше ученик загадывает положительное целое число $$$x \geq 2$$$ и получает балл, равный количеству $$$a_i$$$, которые не являются делителем $$$x$$$. Самат, ученик не простой, и, к счастью, он узнал, какие числа загадает каждый жюри.
Для победы Самату необходим максимальный балл за эту игру, помогите ему найти подходящий $$$x$$$. Для эффектности Самат хочет назвать минимально возможный $$$x$$$.
В первой строке ввода дано число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество жюри на олимпиаде.
Во второй строке ввода даны $$$n$$$ чисел $$$a_1, a_2, ... , a_n$$$ $$$(2 \le a_i \le 10^5)$$$ — числа, которые загадали жюри.
Выведите ответ на задачу.
Всего в задаче $$$50$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 2 балла.
22 3
5
32 3 5
7
В той самой вселенной, где в Уфе появится метро, за постройку метро назначили Ик Билина. Естественно, он хочет сделать это по своему.
Сначала он выбирает число $$$n$$$ и строит первый и самый большой круг метро из $$$n$$$ станций. Дальше он будет строить круговые линии метро, пока это возможно (число делится без остатка) по его формуле $$$a_i = \frac{a_{i - 1}}{i}$$$, где $$$i$$$ — номер круга метро (начинается с 1) и $$$a_i$$$ — количество станций на $$$i$$$-м круге.
Флюр все продумал и понял, что самый последний круг метро должен иметь ровно $$$p$$$ станций, но не продумал, сколько станций должно быть в первом круге метро. К сожалению, он не силен в геометрических прогрессиях и он просит вас узнать, сколько чисел от $$$l$$$ до $$$r$$$ подходит в качестве числа $$$n$$$ (количество станций в первом круге метро) в соответствии с его условием (последний возможный круг равен $$$p$$$).
В первой и единственной строке ввода даны числа $$$l$$$, $$$r$$$ $$$(1 \le l \le r\le 10^{18})$$$ и $$$p$$$ $$$(1 \le p \le 10^{18})$$$.
Выведите ответ на просьбу Ик Билина
Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.
2 18 3
2
В примере подходят 2 числа: 3 и 18.
Первый круг равен 3. 3 не делится на 2, значит первый и последний круг равен 3.
Первый круг равен 18. Второй круг 18 / 2 = 9. Третий круг 9 / 3 = 3. Последний круг равен 3, т.к. 3 не делится на 4.
Вы выступаете в роли тренера команды по Dota 2, и ваша задача — подобрать идеальный набор артефактов для вашего героя. Перед вами строка, представляющая артефакты, которые могут выпасть герою. Однако, некоторые артефакты обозначены символом «x» — это неизвестные предметы, которые могут оказать значительное влияние на силу героя.
Вы можете заменить «x» на различные цифры (каждая из которых обозначает определенный артефакт) так, чтобы в итоге полученное число соответствовало определенной магической энергии.
Чтобы герой мог раскрыть свой потенциал, нужно заменить символ «x» на различные цифры от 1 до 9 (то есть если вы уже заменили какой-то «x» на цифру, то другой «x» уже нельзя заменить на эту же цифру), кроме цифры $$$k$$$ (цифра $$$k$$$ — это тип артефакта, несовместимый с его сборкой).
После замены всех «x» на какие-то цифры применяется операция замены числа на сумму его цифр до тех пор, пока число не станет меньше 10.
После всех этих операций, если полученное число совпадает с цифрой $$$k$$$ и является наименьшим возможным ответом, то ваш герой получает нужный бафф и может продолжить игру, а иначе надо вывести -1.
На первой строке вам даны числа ($$$1 \le n \le 10 ^ 5$$$, $$$1 \le k \le 9$$$), а на второй строке вам дана строка $$$s$$$, состоящая из цифры от 1 до 9 и из символов «x» (их не больше 8 и не меньше 1).
Выведите ответ на задачу
Всего в задаче $$$50$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 2 балла.
5 3x1123
51123
5 35112x
-1
Давайте разберем тесты:
- В первом тесте мы заменим «x» на цифру 5, дальше нам нужно заменить число $$$s$$$ на сумму его цифр, пока оно не будет меньше 10
- $$$s = 51123$$$.
- $$$s = 5 + 1 + 1 + 2 + 3 = 12$$$.
- $$$s = 1 + 2 = 3 = k$$$.
- Во втором примере можно доказать, что нет ответа, а ответ 51123 нам не подходит, потому что мы не можем заменить «x» на цифру 3, так как она совпадает с цифрой $$$k$$$
Быков снова оставил Лобанова на ночное дежурство. Во время ночного дежурства Лобанову нужно решить $$$q$$$ однотипных задач по геометрии.
Задача выглядит так: дан квадрат $$$ABCD$$$ со стороной $$$x$$$, к нему справа достраивается прямоугольный треугольник $$$CDF$$$ с шириной $$$w$$$, сверху строим еще один прямоугольный треугольник $$$BEC$$$, так что его гипотенуза является продолжением гипотенузы первого треугольника, его высоту назовём $$$h$$$. В задаче надо найти площадь большего треугольника $$$AEF$$$.
Романенко решил разыграть Лобанова и во всех задачах замазал $$$h$$$, высоту верхнего прямоугольного треугольника $$$BEC$$$. Лобанов умоляет вас решить его задачки, он даже рассказывает вам что площадь прямоугольного треугольника равна половине произведения его катетов.
Рекомендуем использовать long double в коде на языке c++.
В первой строке дано число $$$q$$$ $$$(1 \le q \le 10^5)$$$
В следующих $$$q$$$ строках, в $$$i$$$-й строке даны $$$x_i$$$, $$$w_i$$$ $$$(1 \le x_i, w_i, \le 10^4)$$$.
Выведите ответы на задачи в отдельных строках.
Ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{−6}$$$
Всего в задаче $$$25$$$ тестов (кроме тестов из условия). Каждый тест оценивается независимо от других в 4 балла.
1 4 8
36.000000