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

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

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль

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

Ответ
 
Опции темы Поиск в этой теме
Старый 06.10.2008, 12:31   #1
Nixond
Пользователь
 
Регистрация: 06.10.2008
Сообщений: 13
По умолчанию Проблема с задачей на перебор..

Здравствуйте!
Для начала, я напишу саму задачу:

Входной файл: input.txt
Выходной файл: output.txt

Ограничение времени на тест: 4 сек
Ограничение памяти на тест: 4 Мб

Условие


В данном двумерном целочисленном массиве a размером N Ч N требуется найти три элемента, сумма которых максимальна. При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.

Формат входного файла

Входной файл содержит число N, за которым следует N2 чисел
a1,1 a1,2 … a1,N
a2,1 a2,2 … a2,N

aN,1 aN,2 … aN,N
— элементы массива.

Формат выходного файла

Выходной файл должен содержать единственное число — максимальную сумму. При N = 1 следует вывести единственный элемент матрицы.

Ограничения

1 ≤ N ≤ 2000, 0 ≤ ai,j ≤ 10^9.

Вот такая задача на перебор..
Есть код, весьма не идеальный, но по сути работающий:

Код:
{$APPTYPE CONSOLE}

uses
  SysUtils;
type
  TIntArray = array [1..2000] of integer; {"строка" матрицы}
var
  fi, fo: text;
  n, i, j, sum, shortn, l, b, e, first: integer;
  a: array [1..50] of TIntArray; {матрица} 
{если матрица будет 2000 на 2000, то в 4 МБ не "влезет", поэтому считываем по 50 "строк"}
//------
procedure ex; {процедура выхода}
  begin
    close(fi);
    assign(fo, 'output.txt');
    rewrite(fo);
    write(fo, sum); {пишем максимальную сумму}
    close(fo);
    halt(0); {выходим}
  end;
//------
begin
  assign(fi, 'input.txt');
  reset(fi);
  read(fi, n); {считываем размер матрицы}
  if n = 1 then {если эл-нт один}
    begin
      read(fi, first); {то читаем его}
      assign(fo, 'output.txt');
      rewrite(fo);
      write(fo, first); {и выводим}
      close(fi);
      close(fo);
      halt(0); {выходим}
    end;
  if n < 50 then {если "войдем" в один массив}
    begin
      shortn := 1; {то пройдем только один раз}
    end
  else
    begin
      shortn := n div 50; {иначе считаем кол-во "проходов"}
      if (n mod 50) <> 0 then
        inc(shortn);
    end;
  sum := 0; {в начале максимальная сумма равна нулю}
  for l := 0 to shortn - 1 do {"проходы", т.е. "перезаписывания" матрицы}
    begin
    b := (1 + 50*l); {начало работы цикла}
    e := (50 + 50*l); {конец}
    for i:= b to e do 
        begin
          if l * i > n then {если эл-тов больше нет, то выходим}
            ex;
          for j := 1 to n do {пробегаем по "строке" матрицы}
            begin
              read(fi, a[i][j]); {считываем очередной эл-нт}
              //vertical
              {если сумма текущих элементов по вертикали больше текущей суммы, то присваеваем другую сумму}
              if (i > 2) and ((a[i][j] + a[i - 1][j] + a[i - 2][j]) > sum) then 
                sum := a[i][j] + a[i - 1][j] + a[i - 2][j];
              //horizont
              {тоже самое, только по горизонтали}
              if (j > 2) and ((a[i][j] + a[i][j - 1] + a[i][j - 2]) > sum) then
                sum := a[i][j] + a[i][j - 1] + a[i][j - 2];
              // |
              //--
              {перевернутой буквой "Г"}
              if (i > 1) and (j > 1) and ((a[i][j] + a[i - 1][j] + a[i][j - 1]) > sum) then
                sum := a[i][j] + a[i - 1][j] + a[i][j - 1];
              //--
              //|
              {буквой "Г"}
              if (i > 1) and (j + 1 <= n) and ((a[i][j] + a[i - 1][j] + a[i - 1][j + 1]) > sum) then
                sum := a[i][j] + a[i - 1][j] + a[i - 1][j + 1];
              //--
              // |
              {зеркальной буквой "Г"}
              if (i > 1) and (j > 1) and ((a[i][j] + a[i - 1][j - 1] + a[i - 1][j]) > sum) then
                sum := a[i][j] + a[i - 1][j - 1] + a[i - 1][j];
              //|
              //--
              {перевернутой, зеркальной буквой "Г"}
              if (i > 1) and (j > 1) and ((a[i][j] + a[i][j - 1] + a[i - 1][j - 1]) > sum) then
                sum := a[i][j] + a[i][j - 1] + a[i - 1][j - 1];
            end;
        end;
    end;

  ex;{вывод результата, выход}
end.
Вопрос в том, что в тестирующей системе, на определенном (10 тесте) происходит ошибка, так называемый "Runtime Error".. - это когда программа завершает свою работу с ненулевым кодом (в Си - return равен не нулю, в Паскале halt - не нуль)..

Лично я не могу разобраться, в чем ошибка.
Прошу вашей помощи!

Последний раз редактировалось Nixond; 06.10.2008 в 12:52.
Nixond вне форума Ответить с цитированием
Старый 06.10.2008, 13:27   #2
Aristarh Dark
Форумчанин
 
Регистрация: 07.08.2007
Сообщений: 154
По умолчанию

Проверяй наличие файла и его длину перед считыванием, скорее всего падает на "пустом" файле.
Aristarh Dark вне форума Ответить с цитированием
Старый 06.10.2008, 13:45   #3
Nixond
Пользователь
 
Регистрация: 06.10.2008
Сообщений: 13
По умолчанию

Спасибо, конечно, попробую!

Но я думаю вопрос все таки не в этом:
просто та тестирующая система не предусмотрена для "подлянок" и прочих "фокусов", входные данные всегда корректны - это 100%!

Конечно может быть ошибка в самом тестирующем ПО, хотя вряд ли, т.к. другие люди смогли сдать эту задачу..

Я больше склоняюсь к ошибке в моем алгоритме...
Nixond вне форума Ответить с цитированием
Ответ


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



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Проблема с задачей по С++ TheWanderer Общие вопросы C/C++ 4 02.10.2008 00:21
Проблема с задачей на одномерный массив в Делфи 7 sting Помощь студентам 34 22.09.2008 15:36
Проблема с задачей diznt Помощь студентам 2 24.08.2008 00:08
как сделать перебор ??? akasex Общие вопросы Delphi 2 13.06.2008 09:27
Перебор элементов матрицы pikkk Общие вопросы Delphi 3 09.05.2008 14:45