Высокоскоростной интернет

Золотая шахта

Команда золотодобытчиков решила разработать золотоносный пласт, который для простоты разделили равномерной сеткой на N×M участков. Для каждого участка экспериментально определили содержание золота в нем.

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

Перед золотодобытчиками встала проблема определения такого участка, чтобы потери золота при взрыве были минимальными. Они поручили эту задачу программисту Мите, но он не справился. Помогите бестолковому программисту решить эту задачу.

Формат входных данных:

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

Формат выходных данных:

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

Пример

Снимок со спутника

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

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

Формат входных данных:

В первой строке входного файла заданы два целых числа N и M (2 ≤ N, M ≤ 500)— размеры карты. В каждой из последующих N строк записано по M символов, причем символ "." обозначает сушу, а символ "#" обозначает воду.

Формат выходных данных:

В выходной файл выведите одно число — количество озер на фотографии.

Пример

Высокоскоростной интернет

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

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

Формат входных данных:

В первой строке входного файла задано целое число N (1 ≤ N ≤ 10⁵). В последующих N строках заданы пары неотрицательных целых чисел — координата дома и радиус действия wi-fi роутера, установленного в нем. Оба числа не превосходят 10⁹.

Формат выходных данных:

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

Пример

Головоломка

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

Имеется доска размером N×M, в некоторых клетках которой лежат фишки. Можно перекладывать фишки в незанятые клетки. Необходимо минимальным количеством перекладываний фишек получить исходную композицию, повернутую на 180 градусов.

Помогите Мите решить головломку, вычислив, какое наименьшее количество перекладываний потребуется для ее решения.

Формат входных данных:

В первой строке входного файла заданы два целых числа N и M (1 ≤ N, M ≤ 100). В последующих N строках записано по M символов, причем, символ "." обозначает пустую клетку, а символ "#" обозначает клетку с фишкой.

Формат выходных данных:

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

Пример

Поиск по сайту: