Информатика

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Возле тропинки растут \(n\) деревьев, текущие уровни влажности которых заданы массивом \(a_1, a_2, \dots, a_n\). Леон научился трем способностям, которые помогут ему осушать и поливать почву.

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(1, 2, \dots, i\) на \(1\).

• Он может выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(i, i + 1, \dots, n\) на \(1\).

• Увеличить уровень влажности всех деревьев на \(1\).

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный \(0\).

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)).

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

Формат выходных данных
Выведите одно целое число — минимальное число действий.

В первом примере из условия достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.

Во втором примере из условия можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).

После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.

 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее W. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет W или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ W-1.

Напишите программу, которая определяет:
задание 1) такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
задание 2)  все значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
задание 3)  все значение S, при котором одновременно выполняются два условия:

Аня и Боря играют в игру. Первый ход делает Аня. Изначально на доске записано натуральное число n. На каждом ходе игрока, этот игрок делает следующий ход:

• выбирает любое x,  не равное n, но кратное числу n (более формально 0 < x < n и n % x == 0)
• заменяет число n на доске на n-x.

Если игрок не может сделать ход, то он проигрывает игру.

Определите, кто победит в этой игре, если оба будут следовать оптимальной стратегии.


Формат входных данных
Программа получает на вход натуральное число n (n <= 1000).

Формат выходных данных
Выведите 1, если Аня выигрывает игру, иначе  выведите 0.

Дан массив целых чисел (nums) с индексацией, начинающейся с 0. Сформируйте новый массив целых чисел (ans), в котором i-й элемент вычисляется по формуле:

 ans[i] = |leftSum[i] - rightSum[i]|.

Где:

leftSum[i] - сумма элементов, стоящих слева от элемента nums[i]. Если таких элементов нет, то leftSum[i] = 0.
rightSum[i] - сумма элементов, стоящих справа от элемента nums[i]. Если таких элементов нет, то rightSum[i] = 0.

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

Формат входных данных
Первая строка содержит число n (n <= 10⁵). Во второй строке записаны n целых чисел numsi - элементы массива nums (|numsi| < 10⁶).

Формат выходных данных
Выведите на экран n чисел - элементы нового массива на экран в одну строку, разделяя элементы одним пробелом.

Электронная почта Деда Мороза в течении долгого времени принимает заказы на новогодние подарки. Все желания детей кодируются некоторым положительным целым числом и затем передаются по каналу связи. Количество заказаов заранее неизвестно, но их всегда не менее двух. Признаком конца данных считается число 0. 
Для того, чтобы понять, что все данные приняты без ошибок, после данных передаётся контрольное значение. Контрольное значение равно максимально возможному произведению двух чисел из переданных, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Дед Мороз очень занят в последний месяц перед Новым годом и просит вас обработать все входные данные и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.


Формат входных данных
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Формат выходных данных
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

Примечание
В последней строке в зависимости от результата (если переданное контрольное значение и вычисленное контрольное значения равны) может быть values true

Максимус любит симметричные строки. В качестве новогоднего подарка, он попросил ему подарить несколько натуральных чисел.  При этом, Максимус будет доволен, если он сможет записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). 
Дед Мороз выбрал для Максимуса N натуральных целых чисел, каждое из которых не больше 1000. Он просит вас помочь ему определить, будет ли доволен Максимус таким подарком.
Если Максимус будет доволен, то ваша программа должна вывести на экран число 1, а иначе - число 0.

Формат входных данных
На вход программе подаётся натуральное число N (N <= 10⁵), а затем N натуральных чисел, каждое из которых не превышает 10000.

Формат выходных данных
Если Максимус будет доволен, то ваша программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Примечание
1. В первом тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры D, 1, 6, 2, 0. Из данных цифр невозможно составить симметричную строку. Ответ: 0.
2. Во втором тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры A, B, 4, 4, A, B, D. Из данных цифр можем составить симметричную строку, например такую AB4D4BA. Ответ: 1.

 

Дед Мороз принёс Алисе новогодний подарок - Бинарную картину, которая представляет собой матрицу размером n x n, где каждое значение равно 0 или 1. Однако, перед тем как положить его под елку, Дед Мороз заметил, что полученная картина немного отличается от той, которую она заказывала.

Чтобы получить картинку, которую хотела Алиса, нужно выполнить следующие два шага:

1. Отразить картинку горизонтально: перевернуть каждую строку матрицы.
2. Инвертировать каждый пиксель: заменить каждое значение 0 на 1 и каждое значение 1 на 0.

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

Помогите Деду Морозу написать программу для посоха, иначе дети могут остаться без новогодних подарков!

Формат входных данных
Программа получает на вход в первой строке число n - размер картины (1 <= n <= 20). В каждой из следующих n строк написано по n чисел 0 или 1. 

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

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

Формат входных данных
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

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

Дана матрица numsi,j размером nxm. Вывести те столбцы матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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

Дана матрица numsi,j размером nxm. Вывести те строки матрицы, в которых имеется хотя бы один элемент, равный минимальному элементу матрицы.

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

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

Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 43, на максимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

Формат выходных данных
Выведите измененную матрицу на экран. Элементы в троке должны разделяться одним пробелом.
 

Дана матрица numsi,j размером nxm. Заменить каждый элемент матрицы, оканчивающийся на 12, на минимальный элемент матрицы. 

Формат входных данных
Программа получает на вход в первой строке два числа n, m - количество строк и столбцов в матрице. В каждой из следующих n+1 строке записаны по m чисел - элементы матрицы numsi,j. (1<= n, m <= 15, -10⁵ <= numsi,j<=10⁵)

Формат выходных данных
Выведите измененную матрицу на экран. Элементы в строке должны разделяться одним пробелом.
 

Пётр любит шахматы и математику. Он знает, что самая мощная фигура в шахматах - это ферзь, потому что он ходит и как ладья, на все клетки на одной с ним вертикали или горизонтали, и как слон, на все клетки по диагоналям. Ферзя можно поставить на доску 8 X 8 так, чтобы он контролировал (то есть мог переместиться в эти клетки за один ход) целых 27 клеток доски!

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁹) - размер доски по вертикали.
Вторая строка входных данных содержит целое число m (1 ≤ m ≤ 10⁹) - размер доски по горизонтали.
Формат выходных данных

Программа должна вывести одно целое число - максимальное количество клеток, которое может контролировать ферзь на доске n x m.

Обратите внимание на то,  что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Замечание
Второй пример из условия приведён на рисунке. Крестиками обозначены клетки, которые контролирует ферзь.

 

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.
Далее идет число k (1<=k<=N) 

Формат выходных данных
Вывести на экран k-й столбец (считая, что нумерация элементов массива начинается с 1, т.е. для первого столбца k=1).
Все элементы выводить в одну строку через 1 пробел между элементами.

Вы замечательный родитель и хотите подарить детям подарки. Но, чтобы не избаловать своих детей, вы должны дать каждому ребенку не более одного подарка.
Каждый ребенок i имеет уровень ожидания равный g[i] - целое число, показывающее минимальный размер подарка, получив который ребенок обрадуется. Каждый подарок j имеет размер s[j]. 
Посчитайте, какое максимальное количество детей вы сможете обрадовать.

Входные данные
Первая строка содержит целое число n - количество детей. Вторая строка содержит n целых чисел g[i] - уровень ожидания i-го ребенка. В третьей строке записано число m - количество подарков. Четвертая строка содержит m целых чисел s[j] - размер j-го подарка.
 

Ограничения

• 1 <= n <= 3 * 104
• 0 <= m <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

Выходные данные
Выведите одно число. Ответ на задачу

Пояснения к примерам
1. В первом примере у вас есть 3 ребенка и 2 подарка. Уровни ожидания детей равны 1, 2, 3, соответственно. Имея 2 подарка размером 1, вы можете обрадовать только того ребенка, чей уровень ожидания равен 1.
Количество таких детей равно одному. Ответ 1.
2. Во втором примере у вас есть 2 ребенка и 3 подарка. Уровни ожидания детей равны 1, 2, соответственно.  3 подарка имеют достаточно большие размеры, чтобы обрадовать всех детей. Ответ 2.

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести. 

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк si; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n. 
 

Ограничения

• 1 <= k <= 600
• 1 <= длина si <= 100
• si состоит только из цифр '0' and '1'.
• 1 <= m, n <= 100

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

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества  {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.

 

Дан набор гирек массой m₁, …, m_N. Можно ли их разделить на четыре кучки равной массы?

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 14. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

Дан набор гирек массой m₁, …, m_N. Разделите его на три кучки равной масссы, содержащие равное число гирек.

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные
Программа получает на вход сумму S. Далее идет число N затем P₁, P₂, ..., P_N. Далее идет число M, затем Q₁, Q₂, ..., Q_M.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите число -1.

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4^{n - 1} грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

Входные данные
В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 10⁹ ) .

Выходные данные
Выведите одно число - количество масс, которые можно измерить с помощью этих гирь.