Информатика

Организаторы TВ-Шоу “Ключ к успеху” подготовили ряд призов для победителей. Если победитель набрал X очков, он должен выбрать призов в точности на X у.е. От предыдущих шоу у организаторов остались N призов стоимостью a₁,a₂,... ,a_n< у.е. соответственно. К сожалению, не известно, сколько именно очков наберет победитель очередной игры. Организаторы решили купить еще M призов, чтобы максимизировать минимальную сумму очков, которую уже нельзя будет набрать имеющимися призами.

Например, если уже имеются призы в 2, 3 и 9 у.е., а покупается 2 приза, то купить надо призы стоимостью 1 и 7 долларов. Тогда победитель сможет набрать себе призы при любом счете от 1 до 22 очков.

Входные данные
В первой строке входных данных находятся два целых числа N и М — число призов у организаторов и число призов, которое они собираются докупить (0 ≤ N ≤ 30, 1 ≤ M ≤ 30). Вторая строка содержит N целых числе в диапазоне от 1 до 10⁹ — стоимости имеющихся призов

Выходные данные
Выведите M чисел — стоимости призов, которые надо купить. Числа следует выводить в порядке неубывания. Если решений несколько — выведите любое из них.

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

Входные данные
На вход подается число n (1 ≤ n ≤ 10¹²).

Выходные данные
Выведите количество счастливых билетов в диапазоне от 1 до n.

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

К несчастью, переключатели не являются доступными. Но Коля нашел сокет, каждый пин которого соединен с одним из переключателей через некоторую схему. Коля нашел эту схему в Интернете. Он обозначил переключатели маленькими латинскими буквами, а пины сокета — большими буквами. После этого он выписал логическую формулу для каждого пина. Согласно этой формуле включенный переключатель представляется значением true, а выключенный —false.

Коля использует в формуле следующие обозначения (операции перечислены от высшего приоритета к нисшему):

• Обозначение пина — буква от ‘A’ до ‘K’ ;
• Скобки обозначают, что если E >— это формула, то (E) — тоже формула;
• Отрицание — ~E— это формула для любой формулы E;
• Конъюнкция — E₁ & E₂ &…&E_n;
• Дизъюнкция — E₁| E₂| … | E_n;
• Импликация Е₁ => E₂ =>… => E_n. Импликации выполняются справа налево: Е₁ => E₂ => E₃ означат Е₁ => (E₂ => E₃);
• Эквивалентность — Е₁ <=> E₂ <=> … <=> E_n. Такое выражение вычисляется так: (Е₁ <=> E₂) &(Е₂<=> E₃) & … &(E_n-1 <=> E_n)..

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

Входные данные
Первая строка входных данных содержит единственное целое число n — количество пинов у сокета (1 < n < 10). Следующие n строк содержат описания каждого пина. Одно описание состоит из обозначения пина и соответствующей формулы, отделенной от обозначения символами ‘:=’. Пин обозначен заглавной латинской буквой. Его формула расположена в одной строке и состоит из элементов ‘a’..‘k’, ‘(’, ‘)’, ‘~’, ‘&’, ‘ |’, ‘=>’ и ‘<=>’. Элементы формулы могут быть отделены друг от друга произвольным числом пробелов. Описание каждого пина содержит не более 1000 символов.

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

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

Дерево Фенвика − это структура данных, эффективно поддерживающая запросы о сумме префикса числового массива. Для числа 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 чисел − элементы видоизмененного массива. Если решений несколько − выведите любое из них.

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

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

Игра имела следующие правила. Алиса выкладывала из кубиков слово S₁. Эти же буквы в зеркале показывали слово S₂, которое могло отличаться от отражения S₁, так как зеркало было заколдованным. Но длина каждого слова равнялась N.

Затем Алиса проделывала следующие шаги. Она выбирала два кубика i и j и меняла их местами. В зеркале при этом менялись изображения кубиков N – i + 1 и N – j + 1 соответственно.

Цель игры — получить из слова S₁ слово T₁, которое будет выглядеть в зеркале как слово T₂. Алиса не знает, когда это возможно, а когда нет. Помогите ей ответить на этот вопрос.

Входные данные
Во входном файле находятся 4 слова S₁, S₂, T₁ и T₂, каждое в отдельной строке. Все слова имеют одну и ту же длину N (1 ≤ N≤ 100) и состоят только из заглавных латинских букв.

Выходные данные
Выведите Yes или No в зависимости от ответа на вопрос задачи.

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

Центробанк Флатландии планирует выделить N пакетов помощи. Каждый пакет характеризуется его суммой A_i.

Банки предоставили запросы на помощь. На данный момент поступило M запросов. Каждый запрос характеризуется его продолжительностью B_i дней.

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

По известной информации о пакетах помощи и запросах подсчитайте количество возможных пар пакет-запрос.

Входные данные
Первая строка содержит целое число N – количество пакетов помощи (1 ≤ N ≤ 100 000). Вторая строка содержит N целых чисел: a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁶).

Вторая строка содержит целое число N – количество запросов (1 ≤ M ≤ 100 000). Вторая строка содержит N целых чисел: b₁, b₂, . . . , b_n (1 ≤ b_i ≤ 10⁶).

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

Комментарий к примеру

Пары могут быть следующие: (3, 1) дважды как (a₁, b₁) и (a₁, b₂), (3, 3), (4, 1) дважды, (4, 2), (5, 1) дважды, (6, 1) дважды, (6, 2) и (6, 3).

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

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

Помогите почтальону составить такой маршрут.

Входные данные
Сначала записано число N — количество площадей в городе (2≤N≤1000). Далее следуют N строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют mi
 пар натуральных чисел: в j-ой паре первое число — номер площади, в которую идет j-ая улица с i
-ой площади, а второе число — длина этой улицы.

Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.

Все числа во входном файле не превосходят 100000

Выходные данные
Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте, а во вторую — номера площадей в порядке их посещения.

Если решения нет, выведите в выходной файл одно число –1.

Если решений несколько, выведите любое.

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

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

Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.

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

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

Входные данные
В первой строке записаны числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).

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

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

• определяет, является ли заданный граф четно-нечетным;
• в случае отрицательного ответа на пункт 1 находит максимальное подмножество X вершин графа такое, что для любых двух вершин i и j из X выполняется следующее условие: все пути между i и j состоят из четного числа ребер.

Входные данные
Первая строка входного файла содержит число вершин графа N (1≤N≤100) и число ребер M (1≤M≤1000), а каждая последующая — пару чисел (i,j), означающих, что в графе присутствует ребро, соединяющее вершины с номерами i и j.

Выходные данные
Первая строка выходного файла должна содержать ответ на пункт 1 в форме «YES/NO». В случае отрицательного ответа на пункт 1 вторая строка должна содержать количество вершин в множестве X, а третья — номера вершин из этого множества в порядке возрастания, записанные через пробел. Если вариантов решений несколько, то достаточно вывести любое из них.

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

Помогите Пете победить опоздания. Город можно представить как N перекрестков, соединенных M улицами, про каждую улицу известна ее длина. Дом Пети находится на перекрестке A, школа - на перекрестке B, а киоск с мороженым - на перекрестке C. По пути в школу Петя никогда не проходит через один перекресток дважды.

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

Первая строка содержит числа N и M (3 ≤ N ≤ 30 000, 0 ≤ M ≤ 50 000). Вторая строка содержит три различных числа - A, B и C. Следующие M строк содержат по три целых числа X_i, Y_i и L_i - номера перекрестков, соединенных улицей и ее длину (длина - целое положительное число, которое не превышает 10⁴).

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

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

В противном случае выведите -1 на первой строке.

Дано N точек на плоскости, их надо покрасить в черный и белый цвета.

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

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

Входные данные
В первой строке задано число 2≤N≤300. В следующих N строках заданы координаты точек.

Выходные данные
Выведите единственное число - количество различных раскрасок.

Есть замок — точка (0,0). Замок окружен несколькими непересекающимися заборами, каждый представляет из себя выпуклый многоугольник.

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

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

Входные данные
8 первой строке задано число N (1≤N≤100000). Далее следуют описания N заборов. Каждое описание начинается с числа K, далее следуют К строк, содержащих по два числа X и Y — координаты вершин (0≤X,Y≤2⋅10⁶). Вершины каждого многоугольника перечисляются в порядке обхода против часовой стрелки. Гарантируется, что точка (0,0) лежит внутри каждого забора.

Далее следует число M (0≤M≤100000) — количество захватчиков. В следующих М строках заданы координаты захватчиков.

Суммарное число вершин во всех многоугольниках не превосходит 100000.

Все вводимые числа являются целыми.

Выходные данные
Выведите единственное число — общую захваченную площадь с шестью знаками после десятичной точки.

На шахматной доске (размером 8 × 8 клеток) стоит несколько ферзей. За один ход разрешается взять одной фигурой другую (цвет фигур значения не имеет; ходы без взятия делать нельзя). Требуется найти последовательность ходов: за каждый ход один из ферзей может взять другого ферзя. В результате доске должна остаться одна фигура. После каждого хода количество ферзей на поле должно уменьшиться.
Ферзь ходит по горизонтали, вертикали или диагонали на любое число клеток. Он не может перепрыгивать через другие фигуры.

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

Выходные данные
В выходной файл выведите возможную последовательность в следующем формате. Для каждого хода указывается сначала клетка, с которой делается ход, затем двоеточие, затем клетка, на которую делается ход. Клетка задается столбцом и строкой: столбцы нумеруются слева направо строчными латинскими буквами a, b, c, d, e, f, g, h; строки — снизу вверх цифрами 1, 2, 3, 4, 5, 6, 7, 8.
Если решений несколько, приведите любое из них. Если решений нет, выведите NO SOLUTION

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


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

В первой строке входного файла вводится одно натуральное число 𝑁≤100 — количество ступенек.
В следующей строке вводятся 𝑁 натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

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

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

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить число безопасных стопок.

Входные данные
Одно число 1≤N≤20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, AC, BA, BB, BC, CA, CB и CC. Стопки типа AA являются взрывоопасными.

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить количество возможных типов безопасных стопок.

Входные данные
Одно число 1 ≤ N ≤ 20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

Определите количество последовательностей из нулей и единиц длины N (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.

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

Выходные данные
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹ − 1.

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

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

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

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

Создатели модного гаджета iDishwasher (обычная посудомоечная машина с нарисованной на ней надкусанной грушей и продающаяся по баснословной цене) решили добавить в стандартную прошивку игру, которая поможет развлечься домохозяйкам, скучающим во время мытья посуды. Игра похожа на шахматы, правда играют в нее не фигурами, а шахматными клетками. В настольной версии игры дается набор черных и белых полей, из которых необходимо составить квадратную шахматную доску максимального размера. В посудомоечной версии игры дается не набор, а количество полей черного и белого цветов. И в качестве ответа нужно не составить доску, а вывести сторону максимального «шахматного» квадрата, который можно составить из данных клеток. Поскольку не вся целевая аудитория справляется с этой интеллектуальной игрой, вам требуется написать программу, которая поможет отчаявшимся пользователям гаджета.

Входные данные
Единственная строка содержит числа B и W задающие количество белых и черных клеток соответственно (0≤B,W≤10000).

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