Для рекламы своей новой продукции в Китае одна компания решила разместить на небоскребе рекламный щит. Щит состоит из лампочек, организованных в форме прямоугольной сетки из \(n\) строк и \(m\) столбцов. В любой момент каждая из лампочек может быть либо включена, либо выключена.
Рекламное сообщение состоит из \(k\) иероглифов, которые будут показываться один за другим. Для каждого иероглифа известно, какие лампочки должны быть включены при отображении этого иероглифа. Остальные лампочки должны быть выключены.
Для управления рекламным щитом разрабатывается специальная система. Система может включать и выключать лампочки целыми группами. Все лампочки разбиваются на несколько групп так, что в каждом иероглифе лампочки из одной группы должны быть либо все включены, либо все выключены.
Для оптимизации работы системы управления необходим разбить лампочки на минимальное возможное число таких групп. Помогите сотрудникам рекламного отдела компании решить эту задачу.
В первой строке входного файла заданы числа \(k\), \(n\) и \(m\) (\(1 \le k, n, m \le 100\)) - количество иероглифов в рекламном сообщении, высота и ширина рекламного щита.
Далее, в \(kn\) строках идет описание иероглифов. Каждый из \(k\) иероглифов задается \(n\) строками по \(m\) символов в каждой. Все эти строки состоят только из символов «*» и «.», «*» соответствует включенной лампочке, «.» - выключенной.
Выведите минимальное число групп, на которое можно разбить лампочки.
В приведенном примере можно разбить лампочки на группы следующим образом: две лампочки из первого столбца образуют одну группу, две лампочки из последнего столбца - вторую, а каждая из двух оставшихся лампочек образует отдельную группу.
3 2 3 *.. *.. **. *.. ... .*.
4
Сегодня Васю заставили убираться в классе. Устав наводить порядок, он решил, что теперь он просто должен в качестве компенсации устроить где-нибудь хаос. И тут ему на глаза попалась написанная учителем на доске перестановка чисел от 1 до \(n\). Напомним, что перестановкой чисел от 1 до \(n\) называется последовательность из \(n\) чисел, в которой каждое из них встречается ровно один раз.
Вася считает, что три подряд идущих элемента находятся в порядке, если они упорядочены либо по возрастанию, либо по убыванию. Он называет перестановку хаотической, если никакая тройка подряд идущих элементов не находится в порядке.
Вася решил изменить перестановку на доске, сделав ее хаотической. Для этого он решил не более \(n\) раз поменять местами два соседних элемента в перестановке.
Помогите Васе сделать перестановку хаотической, пока не пришел учитель и не наказал его за то, что он занимается ерундой вместо уборки.
Во входном файле задана исходная перестановка, которая написана на доске. Первая строка содержит целое число \(n\) - длину перестановки (\(3 \le n \le 1000\)). Вторая строка содержит \(n\) различных целых чисел, каждое из которых лежит в диапазоне от 1 до \(n\) - саму перестановку.
В первой строке выведите число \(k\) - количество операций, которое необходимо сделать Васе. В следующей строке выведите \(k\) чисел - саму последовательность операций. Если на очередном шаге надо поменять местами \(i\)-й и \(i+1\)-й элементы перестановки, необходимо вывести число \(i\).
Если ответов несколько, вы можете вывести любой. Обратите внимание, что вам не обязательно минимизировать количество операций. Достаточно, чтобы оно было не больше, чем \(n\). Если решения не существует, выведите число \(-1\).
5 1 2 3 4 5
2 2 4
Мария Петровна работает преподавателем в университете.
В середине семестра она дала своим студентам контрольную работу, в которой было \(n\) заданий, упорядоченных по возрастанию сложности.
Мария Петровна знает, что каждый из ее студентов относится к одной из трех категорий:
Трудолюбивые и умные студенты всегда правильно решают все задачи, которые успевают.
Мария Петровна очень не любит студентов, которые списывают. Поэтому, если она узнает, что кто-то у кого-то списал, то обоим студентам она эту задачу не засчитывает.
По итогам контрольной Мария Петровна внесла в ведомость зачтенные задачи для каждого студента и про каждую задачу посчитала, скольким студентам она ее зачла.
Поскольку приближаются экзамены, Мария Петровна решила оценить число плохих студентов в группе, чтобы спланировать время на пересдачи. К сожалению, она потеряла ведомость с зачтенными задачами и сохранила лишь листок, в котором записано для каждой задачи, какому числу студентов эта задача зачтена.
Мария Петровна интересуется, какое минимальное число плохих студентов может быть в группе. Помогите ей это выяснить.
Входной файл содержит несколько тестов. В первой строке входного файла содержится целое число \(T\) - число тестов. Далее следуют описания тестов.
Описание каждого теста состоит из двух строк. В первой строке описания задано целое число \(n\) - количество заданий в контрольной работе. Далее для каждого задания, в порядке возрастания сложности, указано число \(a_i\) - количество студентов, которым зачтена соответствующая задача (\(0 \le a_i \le 10^9\)).
Гарантируется, что суммарное число заданий во всех тестах не превосходит \(10^5\), а также то, что в контрольной была хотя бы одна задача.
Для каждого теста выведите единственное число - искомое минимальное возможное число плохих студентов.
В первом тесте у Марии Петровны могло быть три трудолюбивых студента, два из которых решили по две задачи, а один - только одну, и еще один умный студент, который решил самую сложную задачу (но ничего больше решить не успел).
Во втором тесте у Марии Петровны мог быть один умный студент, который решил две последних задачи, четыре трудолюбивых студента, которые решили по две первые задачи и три плохих студента, которые списали первую задачу, каждый у одного из трудолюбивых студентов. В результате из семи решений первой задачи шесть было аннулировано, зачтенным это задание осталось только у трудолюбивого студента, у которого никто не списал.
2 4 3 2 0 1 3 1 5 1
0 3
2 4 3 2 0 1 3 1 5 1
0 3
Часто при вырубке леса для строительства, например, дорог проводятся компенсационные лесопосадки - равное или большее число деревьев высаживается в другом месте. Однако посаженный таким образом лес отличается от самостоятельно выросшего~--- при компенсационной посадке деревья обычно сажают в узлах регулярной решетки, что изменяет влияние деревьев друг на друга.
Павел занимается математическим моделированием роста деревьев, высаженных в узлах прямоугольной решетки.
Будем считать, что в узлы решетки размером \(n\times m\) высажены деревья. Два дерева считаются соседними, если узлы, в которых они растут, являются соседними по вертикали или по горизонтали. У каждого дерева есть своя высота, равная некоторому целому числу метров.
Павел считает, что высота деревьев изменяется с годами по следующему закону:
При моделировании роста деревьев по этим правилам рост всех деревьев остановится в тот момент, когда соседних деревьев с разницей в росте, равной одному метру, не останется. Павел хочет выяснить, сколько лет пройдет до этого момента и какая высота будет в этот момент у каждого дерева.
Помогите ему, напишите программу, которая по заданным начальным высотам деревьев выяснит, через сколько лет рост всех деревьев остановится и какой будет высота каждого дерева в этот момент.
В первой строке входного файла находятся два целых числа \(n\) и \(m\) - размеры участка леса (\(1 \le n, m \le 100\)). Следующие \(n\) строк содержат по \(m\) натуральных чисел, каждое из которых задает высоту соответствующего дерева. Высота каждого дерева не превышает \(100\).
В первой строке выходного файла выведите \(t\) - число лет, которое пройдет до того момента, когда все деревья перестанут расти. После этого выведите \(n\) строк по \(m\) чисел - каждое число должно быть равно высоте соответствующего дерева через \(t\) лет.
3 4 1 1 1 2 1 5 5 1 3 1 1 1
9 3 3 3 3 3 5 5 3 3 3 3 3
Чтобы стать джедаем, необходимо овладеть многими теоретическими и практическим навыками. В Академии Джедаев можно обучиться всему необходимому, если, конечно, у тебя есть способности.
Новый студент академии Фил очень способный и обучается индивидуально. Он вправе самостоятельно составлять свое расписание. Фил очень любознателен, поэтому он все свое время посвящает учебе. Фил не учится только в те моменты, когда переходит из одного корпуса академии в другой или идет из общежития в один из корпусов.
Академия состоит из двух корпусов, в одном из которых обучают теоретическим навыкам, а в другом - практическим. Путь из одного корпуса в другой занимает ровно \(a\) минут. Изучение любого навыка занимает ровно \(b\) минут. В начальный момент Фил находится в общежитии, путь от которого до каждого из корпусов также занимает \(a\) минут.
Разумеется, навыки нельзя изучать в произвольном порядке. Например, прежде чем овладеть световым мечом, нужно сначала изучить основы оптики и искусство рукопашного боя. Филу важно учесть это при составлении своего расписания.
Фил хочет как можно скорее стать джедаем, но для этого ему нужно обучиться всем необходимым навыкам. Прежде чем приступить к учебе, он хочет узнать через какое минимальное число минут он сможет изучить все навыки. Помогите ему это выяснить. После окончания учебы Фил сразу же отправится сражаться со злом, возвращаться в общежитие ему не требуется.
В первой строке входного файла задано целое число \(n\) - количество навыков, которым нужно обучиться в академии (\(1 \le n \le 10^5\)). Все навыки пронумерованы от 1 до \(n\).
В следующих \(n\) строках описаны требования для изучения каждого навыка. В начале \(i\)-й из этих строк записано число 1 или 2, оно указывает в каком корпусе можно изучить \(i\)-й навык. Затем следует число \(k\) - количество навыков, необходимых для изучения навыка \(i\). Затем в этой же строке следует \(k\) целых чисел - навыки, необходимые для изучения навыка \(i\). Гарантируется, что сумма чисел \(k\) по всем навыкам не превосходит \(10^5\).
В следующей строке задано два целых числа \(a\) - время в минутах на путь из одного корпуса в другой или из общежития до корпуса, и \(b\) - время на изучение одного навыка (\(1 \le a, b \le 10^4\)).
Гарантируется, что существует такой порядок изучения всех навыков, при котором каждый раз при изучении очередного навыка все необходимые для него уже изучены.
В единственной строке выходного файла выведите минимальное время в минутах, которое потребуется Филу, чтобы стать джедаем.
6 1 3 3 4 5 2 1 4 2 2 5 6 1 1 6 1 0 1 0 15 40
285