Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.10.2013, 18:27   #1
Simon1712
Пользователь
 
Регистрация: 11.11.2012
Сообщений: 36
По умолчанию Дана прямоугольная целочисленная таблица. Найти четыре ячейки, образующие прямоугольник с максимальной суммой значений

Дана прямоугольная таблица, состоящая из m строк и n столбцов. На пересечении i-й строки и j-го столбца записано целое число aij.

Требуется найти такие четыре различные ячейки таблицы, чтобы их центры были вершинами прямоугольника со сторонами, параллельными сторонам таблицы, а сумма чисел, записанных в этих ячейках, была максимальна.

Формат входных данных
На первой строке записаны два натуральных числа m и n (2 ≤ m, n ≤ 500). Далее следует описание таблицы – m строк, каждая из которых содержит по n целых чисел (-107 ≤ aij ≤ 107).

Формат выходных данных
На первой строке выходного файла выведите целое число r – максимальную сумму выбранных элементов, на второй строке выведите 4 натуральных числа x1, y1, x2, y2 – координаты левой верхней и правой нижней из выбранных ячеек, соответственно (1 ≤ x1 < x2 ≤ m, 1 ≤ y1 < y2 ≤ n). Если оптимальных решений несколько, выведите любое.


Пример
Входные данные

5 5
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 3 1
1 1 1 1 1

Выходные данных

7
2 2 4 4


Помогите решить! НА ум приходит только перебор, но он не зайдет по времени, код можно не писать - главное подать идею решения
Simon1712 вне форума Ответить с цитированием
Старый 12.10.2013, 11:23   #2
cyberdev
Форумчанин
 
Аватар для cyberdev
 
Регистрация: 10.10.2013
Сообщений: 150
По умолчанию

А для чего задачка? Если не секрет.
Сайт о программировании и трехмерной графике - cybersite.ucoz.net
cyberdev вне форума Ответить с цитированием
Старый 13.10.2013, 09:44   #3
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
Сообщение от cyberdev Посмотреть сообщение
А для чего задачка? Если не секрет.
странный Вы...
Ну для чего решают олимпиадные задачи?
В данном случае, скорее всего для того, чтобы получить оценку или зачёт.
А ещё возмножно (хоть и ОЧЕНЬ маловероятно) что TC решает задачу "для себя", чтобы поднять свой программерский скил!

А по сути самой задачи.
я другого варианта решения, кроме перебора, и не вижу.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 13.10.2013, 10:40   #4
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

ИМХО, тут простой перебор.. При таких ограничениях - он будет просто летать..
Просто поставить в левый верхний угол матрицу 2 на 2, посщитать её сумму, запомнить координаты, перенести матрицу на 1 позицию влево, снова найти сумму, если она превышает предыдущую, заменить сумму, заменить координаты.. Когда дошли до конца строки, сдвинуть левый верхний угол "маленькой" матрицы, в позицию (2,1) и снова..
Poma][a вне форума Ответить с цитированием
Старый 14.10.2013, 17:20   #5
cyberdev
Форумчанин
 
Аватар для cyberdev
 
Регистрация: 10.10.2013
Сообщений: 150
По умолчанию

Цитата:
странный Вы...
Ну для чего решают олимпиадные задачи?
В данном случае, скорее всего для того, чтобы получить оценку или зачёт.
А ещё возмножно (хоть и ОЧЕНЬ маловероятно) что TC решает задачу "для себя", чтобы поднять свой программерский скил!
Ну и что здесь странного?
Программист решает задачи ради какого-то результата. К стати, автор так и не ответил.
Сайт о программировании и трехмерной графике - cybersite.ucoz.net
cyberdev вне форума Ответить с цитированием
Старый 14.10.2013, 18:16   #6
Kix.IV
Участник клуба
 
Регистрация: 11.08.2012
Сообщений: 1,226
По умолчанию

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

Вот несколько найденных в сети решений:
Код:
program problem;

uses
	math, sysutils;

const
	maxn = 500;

var
	i, j, m, n: longint;
	a: array [1..maxn, 1..maxn] of longint;
	k, l1, l2, max1, max2, best: longint;
	x1, y1, x2, y2: longint;

begin
	reset(input, 'problem.in');
	rewrite(output, 'problem.out');

	readln(m, n);
	assert((2 <= m) and (m <= 500) and (2 <= n) and (n <= 500));
	for i := 1 to m do begin
		for j := 1 to n do begin
			read(a[i][j]);
			assert(abs(a[i][j]) <= 10000000);
		end;
		readln;
	end;

	best := -maxlongint;
	for i := 1 to m do begin
		for j := i + 1 to m do begin
			max1 := -maxlongint;
			max2 := -maxlongint;
			for k := 1 to n do begin
				if a[i][k] + a[j][k] > max1 then begin
					l2 := l1;
					max2 := max1;
					l1 := k;
					max1 := a[i][k] + a[j][k];
				end else if	a[i][k] + a[j][k] > max2 then begin
					l2 := k;
					max2 := a[i][k] + a[j][k];
				end;
			end;
			if max1 + max2 > best then begin
				best := max1 + max2;
				x1 := i;
				y1 := min(l1, l2);
				x2 := j;
				y2 := max(l1, l2);
			end;
		end;
	end;

	writeln(best);
	writeln(x1, ' ', y1, ' ', x2, ' ', y2);

	close(input);
	close(output);
end.
Код:
{$r-,q-,o+}
{$apptype console}
type
  int = longint;

const
  program_name = 'problem';
  inf = 1000000000;

var
  a: array [1..500, 1..500] of int;
  m1, m2: array [1..500] of int;
  n, m: int;
  u1, u2, i, j, d: int;
  max1, max2, max1i, max2i: int;
  maxi1, maxi2, maxj1, maxj2: int;
  max: int;

begin
  reset(input, program_name + '.in');
  rewrite(output, program_name + '.out');

  read(n, m);
  for i:=1 to n do
    for j:=1 to m do begin
            read(a[i][j]);
            assert(abs(a[i][j]) <= 10000000);
        end;


  for i:=1 to n do
  begin
    m1[i]:=-inf;
    m2[i]:=-inf;
    for j:=1 to m do
    begin
      if (a[i][j] > m1[i]) then
      begin
        m2[i]:=m1[i];
        m1[i]:=a[i][j];
        continue;
      end;

      if (a[i][j] > m2[i]) then
      begin
        m2[i]:=a[i][j];
        continue;
      end;
    end;
  end;

  max:=-inf;
  maxi1:=-1;
  maxi2:=-1;
  maxj1:=-1;
  maxj2:=-1;
  for u1:=1 to n do
    for u2:=u1 + 1 to n do
    begin
      max1:=-inf;
      max2:=-inf;
      max1i:=-1;
      max2i:=-1;
      if (m1[u1] + m2[u1] + m1[u2] + m2[u2] <= max) then
        continue;

      for i:=1 to m do
      begin
        d:=a[u1][i] + a[u2][i];
        if (d > max1) then
        begin
          max2:=max1;
          max2i:=max1i;

          max1:=d;
          max1i:=i;
          continue;
        end;

        if (d > max2) then
        begin
          max2:=d;
          max2i:=i;
          continue;
        end;
      end;

      if (max1 + max2 > max) then
      begin
        max:=max1 + max2;
        maxi1:=u1;
        maxi2:=u2;
        maxj1:=max1i;
        maxj2:=max2i;
      end;
    end;

  writeln(max);
  if (maxj1 < maxj2) then
    writeln(maxi1, ' ', maxj1, ' ', maxi2, ' ', maxj2)
  else
    writeln(maxi1, ' ', maxj2, ' ', maxi2, ' ', maxj1);
end.
Код:
{$o+,q-,r-}
{$APPTYPE console}

uses
    Math, SysUtils;

const
    maxn = 500;
    filename = 'problem';
    inf = $77777777;

type
    int = longint;

var
    n, m, i, j, r, k, k1, k2: int;
    a: array[1 .. maxn, 1 .. maxn] of int;

begin
    reset(input, filename + '.in');
    rewrite(output, filename + '.out');

    read(n, m);
    for i := 1 to n do
        for j := 1 to m do begin
            read(a[i][j]);
            assert(abs(a[i][j]) <= 10000000);
        end;

    r := -inf;
    for i := 1 to n do
        for j := i + 1 to n do begin
            if (a[i][1] + a[j][1] > a[i][2] + a[j][2]) then begin
                k1 := a[i][1] + a[j][1];
                k2 := a[i][2] + a[j][2];
            end
            else begin
                k2 := a[i][1] + a[j][1];
                k1 := a[i][2] + a[j][2];
            end;
            for k := 3 to m do begin
                if (a[i][k] + a[j][k] > k1) then
                    k1 := a[i][k] + a[j][k]
                else if (a[i][k] + a[j][k] > k2) then
                    k2 := a[i][k] + a[j][k];
            end;
            r := max(r, k1 + k2);
        end;

    write(r);
end.

Последний раз редактировалось Kix.IV; 14.10.2013 в 18:20.
Kix.IV вне форума Ответить с цитированием
Старый 14.10.2013, 21:12   #7
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Возможно, если расположить все числа по убыванию, а потом перебором найти максимальные четыре, координаты которых сооставляют прямоугольник, то выйдет немного быстрее чем простой перебор. Но выйгрышь по времени если будет, то будет небольшой и не во всех случаях.
А будет ли вообще это решение правильным?
Poma][a вне форума Ответить с цитированием
Старый 15.10.2013, 11:41   #8
Kix.IV
Участник клуба
 
Регистрация: 11.08.2012
Сообщений: 1,226
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
А будет ли вообще это решение правильным?
Я имел в виду так:
Код:
type
  col = record
    x, y, v: integer;
  end;

var
  m: array of col;
И при сортировке координаты остаются те же. Тут лишь отличие в том, что сначала проверяются наибольшие элементы массива.
Kix.IV вне форума Ответить с цитированием
Старый 24.01.2014, 10:07   #9
Simon1712
Пользователь
 
Регистрация: 11.11.2012
Сообщений: 36
По умолчанию

Разобрался, тему можно закрыть...
Simon1712 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Дана целочисленная прямоугольная матрица. Nastasia_NST Помощь студентам 1 10.05.2012 21:23
Дана целочисленная прямоугольная матрицана C+ Satkoeva Общие вопросы C/C++ 2 10.11.2011 19:09
В квадратной матрице найти столбец с максимальной суммой и строку с максимальной суммой (Pascal) Alexey355 Помощь студентам 1 26.03.2011 14:06
Дана целочисленная прямоугольная матрица. Lollipo Общие вопросы C/C++ 1 12.10.2010 10:52
дана целочисленная прямоугольная матрица Jet-Tea Общие вопросы C/C++ 9 02.06.2010 16:41