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