Класс, в котором учится Дима, отправляется в путешествие! И, конечно же, ребята поедут поездом, в плацкартном вагоне, причём не в обычном, а в инновационном — в нём целых $$$11$$$ плацкартных «купе»! Получив свой билет, Дима задумался, как можно быстро определять тех, кто едет в конкретном плацкартном «купе», а также на боковых местах, расположенных строго напротив этого «купе».
Помогие Диме определить по номеру «купе» расположенные в нём места, а также боковые места, расположенные строго напротив него (для лучшего понимания внимательно изучите рисунок).
Расположение мест в плацкартном вагоне. В первой строке входных данных содержится целое число $$$K$$$ $$$(1 \le K \le 11)$$$ — номер «купе», интересующий Диму.
Выведите шесть целых чисел в порядке возрастания — места, расположенные в соответствующем «купе» и строго напротив него.
В этой задаче $$$10$$$ тестов, не считая теста из условия. За каждый пройденный тест будет начисляться $$$10$$$ баллов.
2
5 6 7 8 63 64
Рядом с домом Пети расположена пекарня, в которой пекут вкусные пирожки с ягодами. Пете очень нравятся три вида пирожков: с брусникой, с черникой и с вишней. Пирожок с брусникой стоит $$$A$$$ рублей, пирожок с черникой стоит $$$B$$$ рублей, пирожок с вишней стоит $$$C$$$ рублей.
Каждый день, проходя мимо пекарни, Петя покупает пирожок одного из этих трёх видов. При этом он соблюдает следующие правила:
Например, если сегодня Петя купит пирожок с брусникой, то завтра он купит пирожок с черникой, послезавтра — пирожок с вишней, на следующий за послезавтра день — пирожок с брусникой, и так далее.
Зная, какой пирожок Петя купит сегодня, определите, сколько денег Петя потратит на пирожки в течение $$$N$$$ дней, начиная с сегодняшнего.
В первой строке входных данных содержится целое число $$$A$$$ $$$\left(1 \le A \le 10^6 \right)$$$ — цена пирожка с брусникой.
Во второй строке содержится целое число $$$B$$$ $$$\left(1 \le B \le 10^6 \right)$$$ — цена пирожка с черникой.
В третьей строке содержится целое число $$$C$$$ $$$\left(1 \le C \le 10^6\right)$$$ — цена пирожка с вишней.
В четвёртой строке содержится целое число $$$N$$$ $$$\left(1 \le N \le 2 \cdot 10^9 \right)$$$ — количество дней, за которые нужно посчитать расходы Пети на пирожки.
В пятой строке содержится число $$$1$$$, $$$2$$$ или $$$3$$$, указывающее, какой пирожок Петя купит сегодня. Число $$$1$$$ соответствует пирожку с брусникой, число $$$2$$$ — пирожку с черникой, число $$$3$$$ — пирожку с вишней.
Выведите единственное целое число — сумму, которую Петя потратит на пирожки.
Обратите внимание, что для больших значений $$$N$$$ ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#)
Решение, правильно работающее только для случаев, когда $$$N \le 3$$$, будет оцениваться в $$$9$$$ баллов.
Решение, правильно работающее только для случаев, когда $$$N \le 1000$$$, будет оцениваться в $$$72$$$ балла.
14 12 11 7 1
88
14 12 11 7 2
86
14 12 11 7 3
85
Во всех примерах цены пирожков и количество дней, в течение которых нужно посчитать расходы Пети на пирожки, одни и те же.
В первом примере первой покупкой Пети будет пирожок с брусникой. Значит, покупки Пети за семь дней могут быть описаны последовательностью брусника, черника, вишня, брусника, черника, вишня, брусника. Сумма, потраченная на покупки, составит $$$14 + 12 + 11 + 14 + 12 + 11 + 14 = 88$$$ рублей.
Во втором примере первой покупкой Пети будет пирожок с черникой. Соответственно, покупки Пети за семь дней могут быть описаны последовательностью черника, вишня, брусника, черника, вишня, брусника, черника. Сумма, потраченная на покупки, составит $$$12 + 11 + 14 + 12 + 11 + 14 + 12 = 86$$$ рублей.
В третьем примере первой покупкой Пети будет пирожок с вишней. Следовательно, покупки Пети за семь дней могут быть описаны последовательностью вишня, брусника, черника, вишня, брусника, черника, вишня. Сумма, потраченная на покупки, составит $$$11 + 14 + 12 + 11 + 14 + 12 + 11 = 85$$$ рублей.
На уроке информатики учитель предложил Васе сыграть в следующую игру.
На доске записаны по порядку все целые числа от $$$1$$$ до $$$N$$$. За один ход можно стереть либо все числа, стоящие на чётных позициях, либо все числа, стоящие на нечётных позициях. После этого оставшиеся числа перенумеровываются заново слева направо; нумерация начинается с единицы.
Игра продолжается, пока на доске есть хотя бы два числа.
Вася выиграет, если после окончания игры единственным оставшимся на доске числом будет число $$$X$$$. Выведите последовательность ходов, которая приведёт к победе Васи. Гарантируется, что Вася всегда может победить.
В первой строке содержится целое число $$$N$$$ $$$\left(2 \le N \le 10^{9}\right)$$$ — начальное количество чисел на доске.
Во второй строке содержится целое число $$$X$$$ $$$\left(1 \le X \le N \right)$$$ — число, которое должно остаться в конце игры.
Выведите последовательность целых чисел, состоящую из чисел $$$1$$$ и $$$2$$$ — ходов Васи. Число $$$1$$$ означает, что Вася стирает все числа на нечётных позициях, число $$$2$$$ — на чётных.
Каждый ход Васи выводите на отдельной строке.
В этой задаче $$$20$$$ тестов, не считая тестов из условия. За каждый пройденный тест будет начисляться $$$5$$$ баллов.
На тесты наложены следующие ограничения:
| Номера тестов | Дополнительные ограничения |
| 1 — 2 | Тесты из условия |
| 3 — 10 | $$$N \le 1000$$$ |
| 11 | $$$X = 1$$$ |
| 12 — 14 | $$$X = N$$$ |
| 15 — 22 | без дополнительных ограничений |
10 5
2 2 1
6 6
1 2 1
Рассмотрим первый пример. На доске записаны числа:
$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$7$$$ $$$8$$$ $$$9$$$ $$$10$$$
Первым ходом Вася стирает все числа на чётных позициях, на доске остаются числа:
$$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$ $$$9$$$
Затем позиции оставшихся чисел перенумеровываются — то есть оставшиеся после первого хода Васи числа получат номера от $$$1$$$ до $$$5$$$. Вторым ходом Вася снова удаляет все числа на чётных позициях, на доске остаются числа:
$$$1$$$ $$$5$$$ $$$9$$$
Третьим ходом Вася удаляет все числа на нечётных позициях, и на доске останется только число $$$5$$$, которое и было нужно.
Во втором примере выписаны числа:
$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$
Вася стирает числа на нечётных позициях, остаются:
$$$2$$$ $$$4$$$ $$$6$$$
Вася стирает число $$$4$$$, которое стоит на чётной позиции. Остаются:
$$$2$$$ $$$6$$$
Вася стирает число $$$2$$$, которое стоит на нечётной позиции. Осталось число $$$6$$$.
Учёные рассматривают участок поверхности Марса, который можно представить в виде последовательности точек с высотами $$$H_1, H_2, \ldots, H_N$$$. Высота между двумя соседними точками меняется равномерно.
Для исследований необходимо собрать информацию с любого отрезка участка поверхности, длина которого равна $$$K$$$. Для этого запланировано выбрать некоторую точку $$$L$$$, высадить туда марсоход и отправить его последовательно по точкам $$$H_L, H_{L+1}, \ldots, H_{L+K}$$$.
Марсоход работает от аккумулятора. На перемещение на одну единицу вверх марсоход тратит одну единицу энергии. При перемещении на одну единицу вниз марсоход накапливает одну единицу энергии. На горизонтальное перемещение энергия не тратится. Изначально у марсохода достаточно энергии, чтобы изучить любой отрезок интересующего учёных участка, а максимальный возможный запас аккумулятора не ограничен.
Учёные хотят, чтобы для дальнейших исследований у марсохода осталось как можно больше энергии. Поэтому среди всех возможных вариантов им нужно найти такое $$$L$$$, чтобы итоговый запас аккумулятора после исследований оказался максимально возможным. Если таких $$$L$$$ несколько, для определённости берется минимальное из возможных.
Помогите учёным найти $$$L$$$.
В первой строке входных данных содержится целое число $$$N$$$ $$$\left(2 \le N \le 250\,000 \right)$$$ — количество точек на интересующем учёных участке поверхности Марса.
Во второй строке содержится целое число $$$K$$$ $$$\left(1 \le K \lt N \right)$$$ — длина отрезка, который должен пройти марсоход.
В следующих $$$N$$$ строках вводятся целые числа $$$H_1, H_2, \ldots, H_N$$$ $$$\left(1 \le H_i \le 10^9 \right)$$$ — высоты точек.
Выведите единственное целое число $$$L$$$ — номер стартовой точки для марсохода.
В этой задаче 25 тестов, помимо теста из условия, каждый из которых независимо оценивается в 4 балла.
Решения, правильно работающие при $$$K = 1$$$, будут оцениваться не менее, чем в 20 баллов.
Решения, правильно работающие при $$$N \le 500$$$, будут оцениваться не менее, чем в 40 баллов.
5 2 1 2 4 3 1
3
В примере из условия марсоход можно высадить в первой, второй или третьей точке.
Если марсоход высадить в первой точке, то при переходе с высоты $$$1$$$ на высоту $$$2$$$ его энергия уменьшится на $$$1$$$. Затем при переходе с высоты $$$2$$$ на высоту $$$4$$$ энергия уменьшится ещё на $$$2$$$, получается, что всего за этот путь заряд энергии уменьшится на $$$3$$$.
Если марсоход высадить во второй точке, то при переходе с высоты $$$2$$$ на высоту $$$4$$$ его энергия уменьшится на $$$2$$$. Затем при переходе с высоты $$$4$$$ на высоту $$$3$$$ энергия увеличится на $$$1$$$, получается, что всего за этот путь заряд энергии уменьшится на $$$1$$$.
Наконец, если марсоход высадить в третьей точке, его энергия сначала увеличится на $$$1$$$, потом увеличится ещё на $$$2$$$, то есть всего за путь увеличится на $$$3$$$.
Таким образом, при равном стартовом заряде батареи максимальный запас у марсохода останется, если его высадить в третьей точке.
Катя очень любит историю, поэтому ей подарили книгу про древние индейские имена. В книге утверждается, что коэффициент древности имени равен количеству таких пар букв имени, что первая буква пары стоит в имени раньше второй, и при этом первая буква пары и в алфавите стоит раньше второй.
Катя так восхитилась данным способом, что сразу же захотела подсчитать древность своего любимого индейского имени.
В первой строке входных данных содержится целое число $$$N$$$ $$$\left(1 \le N \le 10^{5} \right)$$$ — длина любимого индейского имени Кати.
Во второй строке содержится последовательность из $$$N$$$ строчных букв английского алфавита — любимое индейское имя Кати.
Выведите единственное целое число — коэффициент древности имени.
Обратите внимание, что при данных ограничениях ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные числа (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
В этой задаче 30 тестов, не считая теста из условия. Каждый тест будет оценён независимо.
На тесты наложены следующие ограничения:
| Номера тестов | Баллов за тест | Дополнительные ограничения |
| 1 | 0 | Тест из условия |
| 2 – 11 | 2 | $$$N \le 10^3$$$ |
| 12 – 16 | 2 | в имени есть только буквы «a» и «b» |
| 17 – 21 | 2 | все буквы имени записаны по возрастанию их номеров в алфавите |
| 22 – 31 | 6 | без дополнительных ограничений |
7 osceola
6
В примере из условия шесть подходящих пар: символы «o» и «s» на первой и второй позиции, символы «c» и «e» на третьей и четвёртой позициях, символы «с» и «o» на третьей и пятой позициях, символы «e» и «o» на четвёртой и пятой позициях, символы «с» и «l» на третьей и шестой позициях, символы «e» и «l» на четвёртой и шестой позициях соответственно.