Задача на реализацию

Председатель жюри чемпионата по устному счету Иван Владимирович Треугольников придумал новое задание для участников чемпионата. Исходно на доске выписывается \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\). После этого участник должен выполнять команды двух типов:

1. Стереть \(i\)-е число с доски и записать вместо него число \(x\). То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_1, \ldots, a_{i - 1}, x, a_{i + 1}, \ldots, a_n\).

2. Циклически сдвинуть последовательность чисел на \(k\) вправо. То есть, если на доске были записаны числа \(a_1, a_2, \ldots, a_n\), то после выполнения команды числа будут равны: \(a_{n - k + 1}, a_{n - k + 2}, \ldots, a_n, a_1, a_2, \ldots, a_{n - k}\).

После выполнения каждой команды участник должен вычислить сумму всех чисел, записанных на доске, и сообщить ее жюри. Чтобы подготовиться проверять ответы участников, членам жюри необходимо самим вычислить требуемые суммы.

Формат входных данных
В первой строке записано целое число \(n\) — количество чисел, изначально записанных на доске (\(2 \leq n \leq 10^5\)).

Во второй строке через пробел записаны \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) — числа, изначально выписанные на доске (\(-10^9 \leq a_i \leq 10^9\)).

В третьей строке записано целое число \(q\) — количество команд, которые необходимо выполнить (\(1 \leq q \leq 10^5\)).

В каждой из следующих \(q\) строк записана очередная команда в следующем формате:

• \(1~i~x\) — это означает, что участник должен заменить \(i\)-е число последовательности на число \(x\) (\(1 \leq i \leq n\); \(-10^9 \leq x \leq 10^9\)).

• \(2~k\) — это означает, что участник должен циклически сдвинуть последовательность чисел на \(k\) вправо (\(1 \leq k < n\)).

Формат выходных данных
В качестве ответа выведите \(q\) строк, в каждой из которых записано одно целое число.

В \(i\)-й строке должна быть записана сумма чисел на доске после выполнения первых \(i\) команд.

Обратите внимание, что ответ может быть достаточно большим и для его хранения потребуется 64-битный тип данных, int64 в паскале, long long в C++, long в Java.

Замечание
Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: \(4,~1,~2,~1,~5,~3\).

После первой команды последовательность циклически сдвигается на \(3\) элемента вправо. Новая последовательность: \(1,~5,~3,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 3 + 4 + 1 + 2 = 16\).

После второй команды необходимо заменить третий элемент последовательности на число \(10\). Новая последовательность: \(1,~5,~10,~4,~1,~2\). Сумма чисел равна: \(1 + 5 + 10 + 4 + 1 + 2 = 23\).

После третьей команды заменить четвертый элемент на число \(4\). Так как четвертый элемент уже равен \(4\), последовательность не изменяется. Сумма чисел также равна \(23\).

После четвертой команды последовательность циклически сдвигается на \(1\): \(2,~1,~5,~10,~4,~1\). Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна: \(-10,~1,~5,~10,~4,~1\). Сумма чисел в итоговой последовательности равна \(-10 + 1 + 5 + 10 + 4 + 1 = 11\).

Дима купил кладовку размера \(X\times Y \times Z\), где \(X, Y, Z\) — это длина, ширина и высота в метрах соответственно. Но она оказалась без окон, без дверей и с голыми стенами. В магазине продается два типа обоев. В наличии имеется \(S_1\) квадратных метров обоев первого типа, стоимостью \(C_1\) рублей за квадратный метр, а второго типа — \(S_2\) квадратных метров стоимостью \(C_2\) рублей за квадратный метр.

Дима хочет сделать дверь размера \(A \times B\), где \(A\) — ширина, а \(B\) — высота, в одной из стен (обои на дверь клеить не надо). Также он хочет, чтобы на стенах, расположенных друг напротив друга, были наклеены одинаковые обои. То есть обе стены размером \(X \times Z\) должны быть оклеены одним типом обоев. Аналогично, обе стены размером \(Y \times Z\) также должны быть оклеены одним типом обоев. Определите, получится ли у него поклеить обои, и если получится, то какая минимальная сумма в рублях ему потребуется.

Формат входных данных
В первой строке вводится три целых числа \(X\), \(Y\) и \(Z\) (\(1 \leq X, Y, Z \leq 10\,000\)) — длина, ширина и высота комнаты.

Во второй строке вводится четыре целых числа \(S_1\), \(C_1\), \(S_2\) и \(C_2\) (\(1 \leq S_1, C_1, S_2, C_2 \leq 10^{8}\)) — количество квадратных метров обоев первого типа на складе, стоимость квадратного метра обоев первого типа, количество квадратных метров обоев второго типа и стоимость квадратного метра обоев второго типа.

В третьей строке вводится два числа \(A\) и \(B\) (\(1 \leq A, B \leq 10\,000\)) — ширина и высота двери.

Формат выходных данных
Определите, сможет ли Дима оклеить кладовку обоями. Если это невозможно, то выведите -1. Иначе выведите минимальную сумму в рублях, которую Дима потратит на покупку обоев.

Решения, верно работающие при \(X=Y=Z\), будут оцениваться не менее чем в 30 баллов.

Примечание
В первом примере Дима установит дверь в стену размером \(5 \times 10\) и наклеит первый вид обоев на все стены.

Во втором примере Дима установит дверь в стену \(5 \times 10\), наклеит первый вид обоев на стены \(6 \times 10\) и второй вид обоев на стены \(5 \times 10\).

В третьем примере высота двери слишком большая.

В четвертом примере суммарная площадь доступных обоев меньше, чем площадь стен.

Коля любит рисовать картинки из звездочек. Сегодня он решил вывести \(n\) строк, \(k\)-я из которых должна содержать \(k^2\) звездочек.

Но потом Коля понял, что выводить слишком много звездочек плохо. Поэтому он решил, что если в очередной строке надо вывести больше \(100\) звездочек, то он выведет в этой строке только \(100\) звездочек, а затем выведет три точки.

Помогите Коле реализовать его план.

Формат входных данных
На вход подается одно целое число \(n\) (\(1 \le n \le 100\)).

Формат выходных данных
Выведите \(n\) строк в соответствии с планом Коли. Не выводите пробелы.

 

Миша планирует сделать новый сайт для проведения олимпиад по информатике. Он планирует проводить соревнования в трех дивизионах, чем меньше номер дивизиона, тем задачи в нем труднее.

Для того, чтобы определить, какой участник может участвовать в каком дивизионе, планируется использовать рейтинг. Рейтинг каждого участника — целое число от \(0\) до \(5000\).

Для каждого участника, в зависимости от его рейтинга, определен его базовый дивизион.

• Участники с рейтингом от \(0\) до \(1600\) имеют в качестве базового дивизиона третий.

• Участники с рейтингом от \(1601\) до \(1900\) имеют в качестве базового дивизиона второй.

• Участники с рейтингом более \(1900\) имеют в качестве базового дивизиона первый.

Каждое соревнование может проходить в одном или более дивизионах. Каждый участник участвует ровно в одном дивизионе.

• Если соревнование проводится в базовом дивизионе участника, он участвует в своем дивизионе.

• Иначе участник может выбрать, в каком из доступных дивизионов он будет участвовать.

• При этом если рейтинг участника выше, чем рейтинг всех участников, для которых базовым является дивизион, в котором он участвует, он участвует вне конкурса.

По рейтингу участников и списку дивизионов, в котором проводится соревнование, определите, в каких дивизионах он сможет участвовать, и с каким статусом.

Формат входных данных
Первая строка ввода содержит целое число \(r\) "— рейтинг участника (\(0 \le r \le 5000\)).

Вторая строка ввода содержит от одного до трех различных символов. Каждый из этих символов равен 1, 2 или 3. Символы, которые встречаются во второй строке, показывают, в каких дивизионах проводится соревнование. Дивизионы перечислены в порядке возрастания номера, без пробелов.

Формат выходных данных
Выведите одну или более строк. Для каждого дивизиона, в котором участник сможет поучаствовать, выведите номер этого дивизиона. Если участник может принять участие в этом дивизионе только вне конкурса, выведите после номера дивизиона символ <<*>> (звездочка). Выводите дивизионы в порядке возрастания номера.

В этой задаче 35 тестов, каждый тест оценивается независимо, некоторые тесты оцениваются в 2, а некоторые в 3 балла.

В первом примере участник с первым базовым дивизионом должен участвовать в своем дивизионе.

Во втором примере участник со вторым базовым дивизионом может участвовать и в первом и в третьем дивизионе, но в третьем дивизионе его участие будет вне конкурса.

Валентин выписывает натуральные числа, начиная с 1, в виде лестницы: на первой строке он пишет одно число, на второй — два, на третьей — три, и так далее.

1
2 3
4 5 6
7 8 9 10
...

После этого он стирает все числа на каждой строке, кроме первых \(k\). Если в строке меньше \(k\) чисел, он оставляет их все.

Заданы целые числа \(a\) и \(b\), а также число \(k\). Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина.

Формат входных данных

На ввод подаются три строки: первая содержит число \(a\), вторая содержит число \(b\), третья содержит число \(k\) (\(1 \le a \le b \le 10^9\), \(b - a \le 100\), \(1 \le k \le 100\)).

Формат выходных данных
Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина. Числа в строках разделяйте пробелами.

 

Заданы числа \(k\), \(w\), \(h\) и \(t\).

Треуется нарисовать прямоугольную сетку шириной \(w\) и высотой \(h\), ячейки должны иметь размер \(k \times k\), толщина линий должна быть \(t\).

Для линий используйте символ <<*>>, для ячеек используйте символ <<.>>.

Формат входных данных
На первой строке ввода задано целое число \(k\) (\(1 \le k \le 10\)). На второй строке ввода задано целое число \(w\) (\(1 \le w \le 10\)). На третьей строке ввода задано целое число \(h\) (\(1 \le h \le 10\)). На четветрой строке ввода задано целое число \(t\) (\(1 \le t \le 10\)).

Формат выходных данных
Выведите изображение сетки.

В этой задаче 10 тестов, каждый оценивается независимо в 10 баллов.

Возможно, что Вы когда то играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам приходится передавать информацию друг другу различными способами: словесно, образно, бывает даже приходится писать левой рукой текст, который другой участник команды должен будет прочитать. Так же известно, что практически никогда передаваемая информация не доходит до конечного адресата. Обозначим за F_i(x) функцию, которая преобразует текст передаваемой информации x в ту, которую получит участник i+1 от участника i. Тогда последний n-й участник получит данные y, которые будут выражаться следующей формулой:

y = F_n-1(F_n-2(…F₂(F₁(x))))

Но Вам необходимо исключить какие-либо внешние факторы, которые могут исказить исходную информацию и Вы должны реализовать программу «неглухой телефон», которая сможет безошибочно доставлять исходные данные, т.е. в нашем случае функция F_i(x) = x для всех i от 1 до n-1.

Входные данные
В первой строке записано число n от 1 до 100, во второй строке - сообщение переданное первым участником (строка длиной не более 255 символов).

Выходные данные
Выведите значение F(n)

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки.  У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

Входные данные

В первой строке записано три положительных целых числа k, n, w (1  <=  k, w  <=  1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

Выходные данные

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

 

Примеры

№	Входные данные	Выходные данные
1	3 17 4	13

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

• первым числом слева записано число a1;
•  первым числом справа записано число a2;
• вторым числом слева (после a1) записано число a3;
• вторым числом справа (то есть перед числом a2) записано число a4;
• все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.

Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел ai (1 <= ai <= 10⁹) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.
 
 

Примеры

№	Входные данные	Выходные данные
1	6 1 3 5 6 4 2	1 2 3 4 5 6
2	1 23	23

 

Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности, начинающиеся с первого элемента последовательности. Найдите максимальную сумму подпоследовательности, кратную K, и количество таких подпоследовательностей.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁶) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран два числа через пробел: максимальную сумму подпоследовательности, кратную K и количество таких подпоследовательностей.
 

Примеры

№	Входные данные	Выходные данные
1	5 2 2 -2 2 -2 2	2 3

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет.  Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области.  В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей.  Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей.  Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.

Входные данные
На вход подается число h (0 <= h <= 510).

Выходные данные
Выведите число, которое необходимо напечатать.
 

Примеры

№	Входные данные	Выходные данные
1	15	48888888
2	70	88888888888888888888888888888888888

Комната характеризуется тремя целыми числами: длиной, шириной и высотой, заданными в миллиметрах. Комната считается хорошей, если выполнены следующие условия:
отношение меньшей из длины и ширины к высоте хотя бы 2, а также отношение большей из длины и ширины к меньшей не превосходит 2.
По заданным размерам комнаты определите, является ли она хорошей.

Входные данные
На вход подаётся три целых числа: w, l и h — длина, ширина и высота комнаты, каждое
на отдельной строке (1000 ≤ w, l, h ≤ 10 000).

Выходные данные
Если комната является хорошей, выведите «good», иначе выведите «bad».
 

Примеры

№	Входные данные	Выходные данные
1	4000 6000 3000	bad
2	4600 8600 1600	good

На пути к спасению городка Энджел Гроув черный рейнджер Зак Тейлор столкнулся с очередным препятствием. Рейнджер оказался на инопланетном космическом корабле в окружении врагов, и теперь, чтобы освободиться, ему необходимо уничтожить всех врагов в определенном порядке.
Каждый из n врагов обладает силой f_i. Однако среди них имеется главный враг — босс, чья сила равняется сумме сил всех остальных врагов. Так как уничтожение босса требует полной концентрации и сосредоточенности, Зак сможет справиться с ним только после того, как уничтожит всех остальных врагов.
В запасе у рейнджера мало времени, так что он не успевает понять, кто босс. Ему необходима ваша помощь. Восстановите порядок, в котором Заку Тейлору необходимо уничтожать врагов, чтобы выбраться на свободу.

Входные данные
В первой строке находится натуральное число n — количество врагов (3 ≤ n ≤ 10⁵).
Во второй строке находятся n целых чисел f_i, задающих силу каждого врага (-10⁹ ≤ f_i ≤ 10⁹).
Силы врагов заданы в случайном порядке.

Выходные данные
В единственной строке выведите числа f_i в порядке, в котором соответствующие им враги будут уничтожаться рейнджером. Если существует несколько порядков, выведите любой.
Гарантируется, что решение всегда существует, а также существует ровно один враг, который может быть боссом.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 5 3	2 3 5
2	5 -1 1 0 1 -1	-1 1 1 -1 0

Значение выражения \( 27^7 - 3^{11} + 36 - x\) записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100).  Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Результат арифметического выражения \(9^9 – 3^9 + 9^{19} – 19 \) записали в троичной системе счисления. Напишите программу, которая определит количество цифр "2", "1" и "0"в результирующем числе. Выведите ответ в одной строке, через пробел, в указанном порядке.

Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из N ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков.
Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее X, а длинный — на произвольное число, не большее Y (X < Y ). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.
Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех N ступенек.

Входные данные
В первой строке входных данных записано целое число X — максимальная длина короткого прыжка.
Во второй строке записано целое число Y (1 ≤ X < Y ≤ 10¹⁸) — максимальная длина длинного прыжка.
В третьей строке записано целое число N (1 ≤ N ≤ 10¹⁸) — количество ступенек в спуске.

Выходные данные
В единственной строке выведите целое число — минимальное число прыжков, необходимое Марио для спуска.

Примеры

№	Входные данные	Выходные данные
1	2 3 5	2
2	1 2 4	3
3	1 100 1000000000000000000	19801980198019801

Замечание
На изображениях ниже приведены возможные способы решения первых двух тестов из условия:

Напишите процедуру с параметром n, которая выводит ёлочку с кроной высотой n
Основная программа должна содержать ввод значения переменной n и вызов процедуры

Примеры

№	Входные данные	Выходные данные
1	5	o    ooo   ooooo  ooooooo ooooooooo

Дана строка. Получите новую строку, вставив между двумя символами исходной строки символ *. Выведите полученную строку.

Входные данные

Вводится строка.

Выходные данные

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	Pascal	P*a*s*c*a*l

Дана строка. Удалите из этой строки все символы @.

Входные данные: вводится строка.
Выходные данные: выведите ответ на задачу.

 

№	Входные данные	Выходные данные
1	Bilbo.Baggins@bagend.hobbiton.shire.me	Bilbo.Bagginsbagend.hobbiton.shire.me

Замечание: попробуйте использовать метод Replace(Char, Char);