--->
232 задач
<---
Источники
Рано утром Вася решил сделать домашнее задание по информатике. Начать выполнение задания Вася решил с поиска подходящей тетрадки. Добравшись до ящика с чистыми тетрадями, он открыл одну из них. Вася ещё не до конца проснулся и поэтому видит только часть тетрадки и не может сообразить, какая это тетрадка: в клетку, в линейку или в вертикальную линейку. Помогите ему это сделать.
Формально, дана двухмерная таблица из нулей и единиц — часть тетрадки, которую видит Вася. Единицей обозначается закрашенный участок, а нулем — незакрашенный. Назовём вертикальной линией столбец таблицы, все элементы которого — единицы, а горизонтальной линией — строку таблицы, все элементы которой — единицы. Гарантируется, что каждая единица в таблице содержится в какой-либо линии.
Тетрадкой в клетку называется тетрадка, в которой содержатся вертикальные и горизонтальные линии. Тетрадкой в линейку называется тетрадка, в которой содержатся только горизонтальные линии. Тетрадкой в вертикальную линейку называется тетрадка, в которой содержатся только вертикальные линии.
Известно, что в целой тетрадке все расстояния между линиями одинаковы (то есть все клетки — квадраты, все линейки одинаковой ширины). Гарантируется, что линии не могут располагаться рядом (между ними всегда есть промежуток).
Вам требуется написать программу, которая определит тип тетрадки или скажет, что это невозможно однозначно сделать по данной таблице.
В первой строке входных данных даны целые числа n и m (1 ≤ n, m ≤ 1 000) — количество строк и столбцов в таблице. Следующие n строк по m чисел содержат целые числа ai, j (0 ≤ ai, j ≤ 1) — элементы таблицы, задающие видимую часть тетради.
Требуется вывести одну из строк:
3 5
00100
11111
00100
Square
4 5
11111
00000
11111
00000
Line
5 5
00000
00000
11111
00000
00000
?
В данной задаче баллы за каждый тест начисляются независимо от прохождения остальных тестов и суммируются.
Однажды на уроке биологии Петя решил заполнить таблицу n × m числами от 1 до mn по строкам (пример заполнения для n = 3 , m = 4 показан на рисунке). Когда он закончил свой труд, его сосед Коля заинтересовался, можно ли по числу X определить, записано оно на краю таблицы или нет. Помогите Коле.
Под фразой "на краю" имеется в виду, что число X стоит в первом столбце или в первой строке или в последнем столбце или в последней строке.
В первой строке даны два целых числа n и m ( n , m ≤ 20 ). Во второй строке дано одно целое число X ( 1 ≤ X ≤ nm ).
Выведите YES, если число стоит на краю таблицы и NO в противном случае.
3 4 8
YES
3 4 6
NO
Поле Чудес представляет из себя прямоугольную грядку размером n × m лунок, в каждую из которых можно закопать одну монету. Буратино зарыл на Поле Чудес все имевшиеся у него монеты, благоразумно составив карту посадок – звездочками он отмечал лунки, в которых лежат монеты, а точками — лунки без монет.
Теперь его интересует вопрос: а каких лунок больше – с монетами или без? Сколько было у него монет, он, к сожалению, не помнит.
Помогите Буратино справиться с этой задачей.
В первой строке даны два целых числа n и m – размеры грядки ( 1 ≤ n , m ≤ 20 ). В следующих n строках по m символов перечисляется содержимое грядки (точками отмечена пустая лунка, звездочкой – с монетой).
Выведите число 1, если лунок с монетами больше, чем пустых, число 2, если пустых лунок больше, чем полных и число 0, если их количества равны.
3 3 **. .** *.*
1
Крокодил Гена с Чебурашкой играли в какую-то игру, выписывая числа в клетки квадратной таблицы n × n . Однако, когда таблица была заполнена целиком, выяснилось, что правила игры они забыли. Тогда Чебурашка предложил подсчитать числа на главной диагонали квадрата и на побочной диагонали, и если на главной диагонали сумма чисел больше, чем на побочной, то выигрывает Гена, если меньше, то Чебурашка, а если суммы равны, то объявляется ничья.
Таблица была большая и Чебурашка с Геной боятся ошибиться при подсчете. Помогите им определить, чем закончилась игра.
В первой строке дано одно целое число n – размер таблицы ( 1 ≤ n ≤ 20 ). Дальше идут n строк по n неотрицательных чисел в каждой – заполненная после окончания игры таблица. Все числа не превышают 100 .
Выведите 1, если выиграл Крокодил Гена, 2, если выиграл Чебурашка, и 0, если была ничья
3 1 2 3 4 5 6 7 8 0
2
Скоро в Берляндии пройдет очередная Олимпиада. В рамках подготовки к этому важному мероприятию Берляндолимпстрой уже возвел N объектов и теперь хочет разобраться с тем, во сколько Берляндии это обошлось.
Стройка длилась \(K + 1\) день со дня номер \(0\) по день номер \(K\), причем стоимость j-го объекта в нулевой день была равна \(a_j\) бурлям. Однако каждый следующий день стоимость каждого объекта увеличивалась согласно следующему правилу: стоимость j-го объекта в i-й день становилась равна сумме стоимостей всех объектов с номерами, меньшими или равными j, в предыдущий день. Иначе говоря, \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\), где \(S_{i,j}\) — стоимость j-го объекта в i-й день. В итоге на j-й объект было потрачено \(S_{K,j}\) , то есть его стоимость в последний \(K\)-й день. \t{Назовем эту величину итоговой стоимостью j-го объекта.}
Такие увеличения стоимостей проектов для Берляндии не редкость, однако оказалось, что и этих денег не хватило! Выяснилось, что в некоторый день i > 0 стоимость некоторого объекта j дополнительно повысилась на пока не известную следователям сумму X (то есть \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\) + X), что повлияло на стоимости объектов в последующие дни. Следователи выяснили, что из-за этого сумма итоговых стоимостей всех объектов увеличилась на \(R\) бурлей.
Помогите следователям выяснить минимально возможное значение X.
В первой строке входного файла содержатся три целых числа \(N\), \(K\), \(R\): количество олимпийских объектов (\(1 \le N \le 10^5\) ), количество дней увеличения стоимости объектов (\(1 \le K \le 10^5\) ) и количество бурлей, на которое незаконно возросла итоговая сумма (\(1 \le R \le 10^{18}\)). В следующей строке входного файла содержатся N целых чисел \(a_i\) — стоимости объектов в нулевой день (\(1 \le a_i \le 10^9\)).
Единственная строка выходного файла должна содержать единственное целое число — минимально возможное значение \(X\)
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оцениваемый в ноль баллов.
1. Тесты 2—25. В тестах этой группы \(N \le 10, K \le 10, a_i \le 10\), искомое значение \(X\) не превосходит \(10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 26—38. В тестах этой группы \(N \le 1 000, K \le 1 000\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются \t{независимо}
3 3 12 1 3 3
2