Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Из нижеприведенных правил выберите правило с наибольшим приоритетом:

1) footer .social-links a[target="_blank"]
2) #footer a
3) a:hover
4) a

Для поиска полезных ископаемых ученые разработали специальный сканер.

Представим область для поисков как таблицу из \(k\) строк и \(n\) столбцов. Нумерация строк идет от \(1\) до \(k\) сверху вниз, нумерация столбцов от \(1\) до \(n\) слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

Формат входных данных
В первой строке даны два числа \(n\), \(k\) — количество столбцов и строк, соответственно (\(1 \le n \le 200\), \(1 \le k \le 7\)).

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

битмаски Динамическое программирование: один параметр реализация

✓ 1✗ 01 200средняяВойти и решать

Все на съезд!#60136

В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по вопросам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь организаторам необходимо распределить секции по дням: в каждый день будут проводиться 4 секции.

Известно, что в съезде примут участие \(n\) человек. Каждый участник съезда выбрал 3 секции, которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно, каждый участник в один день может присутствовать не более чем на одной секции. Поэтому если в один день будут идти две или три секции, выбранные каким-то участником, то он всё равно сможет посетить только одну из них. Если же выбранные секции будут проходить в разные дни, участник сможет посетить их все.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 10\,000\)) — количество участников съезда.

В каждой из следующих \(n\) строк даны \(3\) попарно различных натуральных числа, не превосходящие \(12\), — номера секций, которые хочет посетить один из участников.

Формат выходных данных
Программа должна вывести \(3\) строки, в каждой из которых должны быть \(4\) числа через пробел — номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний несколько, можно вывести любое из них.

Примечание
В примере из условия расписание составлено так, что второй и третий участник посетят все желаемые секции, а первый — две секции (\(5\) и одну из секций \(1\), \(6\)). Таким образом, суммарно будут посещены 8 секций. Можно показать, что этот результат улучшить нельзя.

битмаски Перебор реализация

✓ 3✗ 101 100средняяВойти и решать

Вывод всех выравниваний - 2#59888

Напишите программу, которая выполняет глобальное выравнивание двух ДНК-последовательностей, и выводит все выравнивания и их score (балл).

Формат входных данных
Две строки содержит две последовательности ДНК, далее вводятся настройки параметров:

Балл за совпадение
Балл за несовпадение
Балл за открытие гэпа
Балл за продолжение гэпа

Формат выходных данных
Выведите все выравнивания.

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

✓ 11✗ 19600лёгкаяВойти и решать

Вывод всех выравниваний#59885

Формат входных данных
Две строки содержит две последовательности ДНК.
Формат выходных данных
Выведите все выравнивания и их score (балл).

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

✓ 11✗ 24500лёгкаяВойти и решать

Задача №1#58619

Нарисуйте из символов или напишите что-нибудь красивое и выведите это. Вы получите ОК, если проверяющая система согласится, что это красиво, и WA, если не согласится.

реализация

—Войти и решать

3#58515

реализация Строки

✓ 1✗ 28—Войти и решать

Дано дерево#57754

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.
Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

Деревья Задачи на моделирование реализация

✓ 1✗ 0—Войти и решать

Опечатки#56662

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

Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго - удалением буквы "r".

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

Входные данные
В первой строке входного файла через пробел записаны натуральные числа N ≥ 1 - общее количество слов в словаре и M ≥ 1 - количество слов в проверяемом тексте (N+M ≤ 20000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

Выходные данные
Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).

Пересечение множеств реализация Хеш

—Войти и решать

Сигнализация#56315

Подземный бункер состоит из \(n\) комнат, соединённых \(n - 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(\rho(i, j)\).

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, расстояние до которой не превосходит расстояние \(d_i\), определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(\rho(i, j) \leq d_i\). Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

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

Требуется написать программу, которая определяет минимальное количество сирен в наборе, удовлетворяющем правилам безопасности.

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

Первая строка входных данных содержит единственное число \(n\) — количество комнат.

Вторая строка содержит последовательность из \(n\) целых чисел \(d_i\), \(i\)-е из них равно максимальному расстоянию, на котором расположенная в комнате \(i\) сирена активирует датчики (\(0 \leq d_i \leq 10^9\)).

Последующие \(n - 1\) строк описывают коридоры бункера. В \(i\)-й из них находятся три целых числа: \(u_i\), \(v_i\), \(l_i\), где \(u_i\), \(v_i\) — номера различных комнат, соединённых коридором \(i\), а \(l_i\) — длина этого коридора (\(1 \leq u_i, v_i \leq n\); \(1 \leq l_i \leq 10^9\)).

Выходные данные
Выходные данные должны состоять из единственного числа — минимального количества сирен, которые необходимо включить вручную.

Замечание
В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.

графы реализация Центроиды

✓ 1✗ 0—Войти и решать

Подводная лодка#56309

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по \(w\) элементов в каждой строке.

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

<<корпус>> — полоса из элементов с координатами от \((x_1, y_1)\) до \((x_2, y_1)\), где \(x_1 < x_2\);
<<рубка>> — полоса из элементов с координатами от \((x_3, y_1)\) до \((x_3, y_2)\), где \(x_1 \leq x_3 < x_2\); \(y_1 \leq y_2\);
<<хвост>> — полоса из элементов с координатами от \((x_4, y_3)\) до \((x_4, y_4)\), где \(x_3 < x_4 \leq x_2\); \(y_3 \leq y_1 \leq y_4\).

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

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

Входные данные
Для сжатия передаваемых со спутника данных каждый элемент снимка кодируется строчной буквой английского алфавита. Первая строка входных данных содержит число \(k\) — количество использованных для кодирования букв (\(k \le 26\)). Вторая строка входных данных содержит \(k\) целых чисел \(c_i\) — значения отклонений соответствующих каждому кодовому символу по порядку букв в английском алфавите от 1 до \(k\)-й.

Третья строка входных данных содержит числа \(h\) и \(w\) — размеры снимка. Последующие \(h\) строк содержат по \(w\) символов — кодовые значения элементов снимка.

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

Примеры

№	Входные данные	Выходные данные	Изображение
1	2 -10 1 6 11 aaaaaaaaaaa aaabaaaaaaa aaabaaaabaa abbbbbbbbba aaaaaaaabaa aaaaaaaaaaa	13	........... ...b....... ...b....b.. .bbbbbbbbb. ........b.. ...........
2	3 -4 -3 4 5 5 bbabc ccaac accba baccb baaaa	16	..... .c... .cc.. ..c.. .....
3	3 -2 4 0 5 5 abccb cccac cbcba cccbb accba	24	.b... .c... .b.b. cccbb ...b.
4	4 -1 -5 -3 0 5 5 bbabc ccaac acdba baccb baaaa	-2	..... ..aa. ..... ..... .....

Пояснение

Для примера ниже приведены несколько потенциальных изображений подводной лодки.

Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки:

Префиксные суммы(минимумы, ...)реализация

✓ 2✗ 0—Войти и решать

Вышивка жемчугом#56299

Со стародавних времён в поморских деревнях рукодельницы вышивали жемчугом на прямоугольных полотенцах, состоящих из одинаковых клеток. Вышивка начиналась с пришивания жемчужины к полотенцу в центре одной из клеток. Чтобы пришить новую жемчужину, рукодельница делала стежок из клетки, уже содержащей жемчужину, в соседнюю с ней по горизонтали или вертикали свободную клетку. Новая жемчужина пришивалась в центре клетки на конце стежка. Этот процесс повторялся, пока не заканчивались жемчужины.

Одно из таких праздничных полотенец находится в музее. К сожалению, некоторые части узора были утеряны, но описание полотенца сохранилось. Дирекция музея планирует восстановить один из прямоугольных фрагментов полотенца, но не ещё не решила какой именно. Затраты на восстановление фрагмента зависят от количества связных частей узора, попавших на этот фрагмент. Часть узора считается связной, если от любой её жемчужины можно по стежкам перейти к любой другой её жемчужине, не выходя за границы фрагмента. Дирекция всегда относит любые две жемчужины, между которыми можно перейти по стежкам, к одной и той же связной части узора.

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

Входные данные
Первая строка входных данных содержит два целых числа \(a\) и \(b\) — размеры полотенца в клетках по горизонтали и вертикали.

Вторая строка содержит два числа \(n\) и \(q\) — количество жемчужин в узоре и количество фрагментов соответственно.

Следующие \((n - 1)\) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

h \(x~y\) означает, что клетки с координатами \((x, y)\) и \((x + 1, y)\) содержат жемчужины, соединённые горизонтальным стежком (\(1 \leq x \leq a - 1\); \(1 \leq y \leq b\));
v \(x~y\) означает, что клетки с координатами \((x, y)\) и \((x, y + 1)\) содержат жемчужины, соединённые вертикальным стежком (\(1 \leq x \leq a\); \(1 \leq y \leq b - 1\)).

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

Следующие \(q\) строк описывают фрагменты. Каждое описание содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\) — координаты левой нижней и правой верхней клетки фрагмента (\(1 \leq x_1 \leq x_2 \leq a\); \(1 \leq y_1 \leq y_2 \leq b\)).

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

Замечание
Пояснение к тесту из условия.

графы поиск в глубину и подобное реализация

✓ 1✗ 0—Войти и решать

Памятник#56262

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера \(1 \times k\). Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты \((0, 0)\), то левые нижние углы плиток будут иметь координаты \((i \cdot k+j,j)\) для всех целых \(i\) и \(j\).

На площади было решено установить памятник известному архангельскому писателю и художнику Писахову. Для установки памятника необходимо удалить все плитки, полностью или частично попадающие под его основание. Основание памятника имеет форму многоугольника с целочисленными координатами вершин, все стороны которого параллельны осям координат. Известно, что любая прямая, пересекающая основание памятника и параллельная одной из осей координат, в пересечении с основанием образует один отрезок.

Для установки памятника необходимо выбрать место на площади таким образом, чтобы количество удалённых плиток было минимальным. При выборе места основание разрешается только передвигать параллельно осям координат.

Требуется написать программу, вычисляющую минимальное количество плиток, которые придётся .

Входные данные
Первая строка входных данных содержит два числа \(n\) и \(k\) — количество вершин в основании памятника и размер плитки.

Каждая из последующих \(n\) строк содержит два целых числа \(x_i\), \(y_i\) — координаты \(i\)-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

Замечание

Задачи на моделирование Отрезки реализация

✓ 1✗ 0—Войти и решать

Разноцветные треугольники#56222

Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.

Требуется привести любую из допустимых раскрасок.

Входные данные
В первой строке записано одно число N (4≤N≤100) - количество вершин многоугольника.

Далее следуют N–3 строки, в каждой из которых записана пара натуральных чисел — номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.

Выходные данные
В выходном файле должны быть 2N–3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.

Конструктив реализация

✓ 1✗ 0—Войти и решать

ООП-3#55919

Каким термином из ООП можно охарактеризовать универсальность интерфейса доступа к разным типам данных?

стандартизация
унификация
наследование
полиморфизм
инкапсуляция

реализация

—Войти и решать

Злой лифт#55504

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:

- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж

Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

Входные данные
Первая строка содержит число N – высоту небоскреба (1 <= N <= 10¹⁸).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

Выходные данные
Выведите единственное число — оценку адекватности Артемия Индюкова.

кратчайшие пути реализация теория чисел

✓ 1✗ 0—Войти и решать

Кеннинги#55465

Кеннинг – это форма поэтической метафоры в древности, когда одно слово заменяется словосочетанием (двумя или более словами). Например, “giver of the gold” – это кеннинг для слова “warrior”. Причем нет разницы в использовании слова и его кеннинга: “poor giver of the gold” и “poor warrior” – это одно и то же. Кеннинги могут быть вложенными. Так, “serpent’s lair” означает “gold”, поэтому “giver of the serpent’s lair” означает “warrior”.

Для зачета вам надо создать достаточно длинный текст. Это можно сделать быстро, имея план текста и список кеннингов. Будем использовать следующий алгоритм. Если текст уже достаточно длинный, то задание выполнено. В противном случае одновременно заменяем все слова в тексте, имеющие кеннинги на соответствующие кеннинги, затем алгоритм повторяется снова.

Входные данные
В первой строке входных данных содержатся 3 числа: ширина результирующего текста w (1≤w≤255), минимальное число непробельных символов в тексте l (1≤l≤3000) и число кеннингов в списке n (1≤n≤380). Далее следует список кеннингов, по одному в строке. Каждая строка сначала содержит заменяемое слово, а за ним следует соответствующее словосочетание. В конце входных данных в одной или нескольких строках содержится план текста.

Каждый кеннинг содержит по крайней мере 2 слова (т.е. одна строка содержит не менее трех слов). Кеннинги могут быть рекурсивными. Например, кеннинг для слова “GNU” может быть таким “GNU is Not UNIX”. Кеннинги чувствительны к грамматическим формам и даже к регистру букв, так слова “warrior”, “Warrior” и “warriors” различны и могут иметь разные кеннинги.

Входной файл не превосходит 3 000 байт и содержит только английские буквы, подчеркивания, пробелы, переводы строки и, в первой строке, цифры. Одно слово имеет только один кеннинг. Все слова состоят не более чем из w
символов.

Соседние слова разделены в точности одним пробелом или переводом строки. Ни в одной из строк нет ведущих или хвостовых пробелов.

Выходные данные
Если алгоритм не даст результата, то выведите слова “No result” в единственной строке.

В противном случае выведите полученный текст, размещая не более w символов (включая пробелы) в строке. Все переводы строки из первоначального плана должны быть сохранены. Перед очередным словом надо вставить перевод строки, если оно не уместиться в текущей строке. Соседние слова должны быть разделены ровно одним пробелом. В строках не должно быть ведущих и хвостовых пробелов. В корректном тексте не будет больше 10 000 байт.

Задача на реализацию Задачи на моделирование реализация

✓ 1✗ 0—Войти и решать

Дерево Фенвика#55452

Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа t обозначим h(t) максимальное значение k, такое что t делится на 2k. Например, h(24)=3, h(5)=0. Обозначим l(t)=2h(t), например, l(24)=8, l(5)=1.

Рассмотрим массив a[1], a[2], … , a[n] целых чисел. Дерево Фенвика для этого массива — это массив b[1], b[2], …, b[n], такой что \( \sum\limits_{j=i-l(i)+1}^{i}a[j] \) Таким образом: b[1]=a[l], b[2]=a[l]+a[2], b[3]=a[3], b[4]=a[l]+a[2]+a[3]+a[4], b[5]=a[5], b[6]=a[5]+a[6], Например, дерево Фенвика для массива a=(3,−1,4,1,−5,9) есть массив b=(3,2,4,7,−5,4).

Назовем массив само-фенвиковским, если он совпадает со своим деровом Фенвика. Напрмер, массив a=(0,−1,1,1,0,9) таковым является.

Вам дан массив а. Вам разрешается заменять в нем некоторые элементы, не меняя их порядка, чтобы сделать из исходного массива само-фенвиковский. Количество изменений при этом должно быть минимально возможным.

Входные данные
В первой строке входных данных содержится количество чисел в массиве n (1 ≤ n ≤ 100000). Во второй строке находятся сами n целых чисел. Все числа по модулю не превосходят 10⁹.

Выходные данные
Выведите n чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.

Дерево Фенвика реализация

✓ 1✗ 0—Войти и решать

Цветной прямоугольник#55409

Дан прямоугольник m×n, клетки которого раскрашены в три цвета. Можно выбрать квадрат 2×2 и, если в нем какой-то цвет преобладает,перекрасить весь этот квадрат 2×2 в этот цвет.Если в нем по две клетки двух цветов, то все его клетки можно перекрасить в третий цвет. Требуется такими операциями перекрасить весь прямоугольник в один цвет.

Входные данные
Числа m, n (3≤m,n≤100) и раскрашенный прямоугольник. Прямоугольник задается набором из m строк, в каждой из которых n символов (R, G или B).

Выходные данные
Последовательность перекрашиваемых квадратов (не более 10mn
операций),
по одному перекрашиванию в строке. Каждое перекрашивание задается
парой чисел~--- номером строки и столбца левого верхнего
квадрата в перекрашиваемом прямоугольнике.

реализация

—Войти и решать

Сортировка ожерелья#55202

Ожерелье представляет собой нитку, на которую надето N различных бусинок. У нитки два конца: левый и правый. С бусинками на нитке можно делать следующие операции:

ML (move left) – снять крайнюю левую бусинку и надеть ее на правый конец нитки. По сути, при этом происходит циклический сдвиг ожерелья.
MR (move right) – снять правую бусинку и надеть ее на левый конец.
RL (remove left) – снять крайнюю левую бусинку и положить ее на стол (не одевать на нитку).
RR (remove right) – снять крайнюю правую бусинку и положить ее на стол.
PL (put left) – взять со стола бусинку и надеть ее на левый конец нитки.
PR (put right) – взять со стола бусинку и надеть ее на правый конец нитки.

На столе может лежать не более одной снятой бусинки, то есть после операции RL или RR нельзя использовать другую операцию RL или RR, пока не будет выполнена операция PL или PR.

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

Входные данные
Программа получает на вход количество бусинок в ожерелье N ≤ 500. Далее идет некоторая перестановка чисел 1, . . . , N, задающая номера бусинок, расположенных на нитке. Номера перечислены слева направо.

Выходные данные
Программа должна вывести последовательность команд ML, MR, RL, RR, PL, PR, которая переводит исходную перестановку бусинок к перестановке 1, . . . , N.

Задачи на моделирование реализация

✓ 1✗ 0—Войти и решать