Женя — большой любитель путешествий, поэтому в качестве подарка на Новый Год родители решили свозить его в Сочи. Женя очень обрадовался и сразу побежал собирать все необходимые для поездки вещи. Так как он уже совсем взрослый, то родители выделили ему отдельный чемодан. Женя тут же попытался его открыть, чтобы побыстрее начать закидывать в него свои вещи, но обнаружил, что чемодан обладает специальным кодовым замком.
Замок представляет собой 3 диска с цифрами, на каждом диске нанесены все цифры от 0 до 9 по кругу. При этом замок устроен так, что одновременно видны только 3 цифры (по одной с каждого диска), которые и образуют код. За одну секунду можно повернуть любой диск на одну цифру в любую сторону. Например, если сейчас на чемодане выставлен код 340, то за одну секунду можно повернуть первый диск вперед и получить 440, а можно повернуть третий диск на одну цифру назад и получить 349. Таким образом, за одну секунду из кода 340 можно получить следующие коды: 240, 440, 330, 350, 341, 349. Родители подсказали Жене, что чемодан откроется, если все цифры кода станут одинаковыми (например, 000 или 444).
Так как Жене уже не терпится поскорее начать собираться в поездку, он хочет открыть чемодан как можно быстрее. Напишите программу, которая поможет ему вычислить, какое минимальное количество времени потребуется, чтобы открыть чемодан.
В трех строках вводятся 3 цифры начальной конфигурации замка, каждая записана в новой строке.
В единственной строке выведите одно число — минимальное число секунд, за которое Женя сможет открыть свой чемодан.
3 4 5
2
0 0 9
1
В первом тесте можно доказать, что быстрее всего можно выставить код 444. Для этого достаточно повернуть первый диск на одну цифру вперед, после чего повернуть последний диск на одну цифру назад. Итого для открытия чемодана нужно 2 секунды и последовательность кодов на замке может выглядеть так: 345, 445, 444.
Во втором тесте достаточно повернуть последний диск на одну цифру, чтобы получить код 000.
В мире существует огромное количество горных систем. Самые высокие из них, как правило, образовались в течение последних 50 млн. лет и называются молодыми. Ученые собрали статистику о высоте гор в виде неубывающего массива чисел — $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$, означающих высоты гор в сантиметрах.
Оказалось, что можно предсказать высоты гор в будущем. Для каждого года $$$j$$$ в течение $$$q$$$ последующих лет ученые предположили, что $$$k_j$$$ самых высоких гор вырастут на $$$x_j$$$ сантиметров.
Ученые предоставили вам необходимую информацию и попросили вас узнать, какими будут высоты гор через $$$q$$$ лет. Напишите программу, которая поможет найти искомые высоты.
На вход в первой строке подается натуральное число $$$n$$$ $$$(1 \leqslant n \leqslant 10^5)$$$ — количество исследуемых гор. Во второй строке идут $$$n$$$ чисел — $$$a_i$$$ $$$(1 \leqslant a_i \leqslant 10^9)$$$ — текущие высоты гор в сантиметрах.
В третьей строке находится число $$$q$$$ $$$(1 \leqslant q \leqslant 10^5)$$$ — количество последующих лет, в которые происходили изменения. Каждая из следующих $$$q$$$ строк состоит из 2 чисел — $$$k_j$$$ и $$$x_j$$$ $$$(1 \leqslant k_j \leqslant n$$$, $$$1 \leqslant x_j \leqslant 10^4)$$$, где $$$k_j$$$ — количество самых высоких гор, которые вырастут в $$$j$$$-й год, а $$$x_j$$$ — высота, на которую они увеличатся.
Нужно вывести $$$n$$$ чисел — высоты гор через $$$q$$$ лет в сантиметрах в порядке неубывания чисел.
3 1000 2000 3000 2 2 2000 1 3000
1000 4000 8000
В первом примере всего 3 горы высотой 1000, 2000 и 3000 сантиметров. В следующем году высоты второй и третьей гор увеличатся на 2000 сантиметров, а через год — вырастет только третья гора на 3000 сантиметров
На уроке информатики Маша и Петя узнали, что любое натуральное число представимо в виде суммы различных степеней двойки единственным образом. Таким образом у них появилась идея модернизации тарифов сотовых операторов. Действительно, почему бы не продавать пакеты по 1, 2, 4, 8, ... минут разговоров, чтобы каждый мог набрать столько минут, сколько ему нужно?
Согласовав все тонкости, Маша с Петей предложили однокласснику Вите тарифный план, состоящий из $$$n$$$ предложений: $$$i$$$-е предложение (начиная с 0) представляет собой пакет на $$$2^i$$$ минут со стоимостью $$$a_i$$$ рублей, причем из соображений адекватности цены $$$a_i \leqslant 2^i$$$ и $$$a_i \leqslant a_{i + 1}$$$.
Вите нужны хотя бы $$$k$$$ минут разговоров для его нужд, и, естественно, он хочет сэкономить как можно больше денег. Напишите программу, которая выведет минимальное количество денег, которые необходимо потратить Вите по тарифному плану Маши и Пети, если можно покупать несколько одинаковых пакетов.
В первой строке ввода дается одно число $$$k$$$ $$$(1 \leqslant k \leqslant 10^9)$$$ — количество минут разговоров, необходимых Вите. Во второй строке находится число $$$n$$$ $$$(1 \leqslant n \leqslant 100)$$$ — количество тарифов, предлагаемых Машей и Петей. В третьей строке находятся $$$n$$$ чисел — $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ $$$({1 \leqslant a_i \leqslant \text{min}(2^i, 10^9)}$$$, $$${a_i \leqslant a_{i + 1}})$$$ — стоимости соответствующих пакетов минут.
Выведите одно число — минимальное количество денег (в рублях), которое необходимо Вите, чтобы суммарное количество минут в купленных пакетах было не меньше $$$k$$$.
Гарантируется, что решения, корректно работающие при ограничении $$$k \leqslant 10^7$$$, будут оцениваться исходя из 75 баллов.
23 5 1 2 3 7 16
18
В примере пакет на 1 минуту стоит 1 рубль, на 2 минуты — 2 рубля, на 4 минуты — 3 рубля, на 8 минут — 7 рублей и на 16 минут — 16 рублей. Выгоднее всего взять 6 пакетов по 4 минуты (суммарно 24 минуты), тем самым Вите необходимо иметь хотя бы $$$6 \times 3 = 18$$$ рублей.