Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Спиральный обход с выводом строки

Автор: obsidium 15.10.2010, 12:34

Привет всем,столкнулся вот с такой задачей:

http://imcs.dvgu.ru/cats/main.pl?f=problem_text;cpid=715083;sid=RtKf3upCs5Z0Muoe6zr1EC8fpd7nor;cid=715078

Задача B. Спираль

Входной файл:    input.txt        Ограничение времени на тест:    1 сек
Выходной файл:    output.txt        Ограничение памяти на тест:    64 Мб

Условие:

Квадратная матрица размера n*n заполнена целыми числами от 1 до n*n следующим образом.
В левом верхнем углу находится число n*n.
Остальные числа, начиная от n*n-1 вплоть до 1, располагаются в порядке убывания по спирали, закрученной по часовой стрелке.

Например, при n = 2 и n = 3 матрица принимает вид:
4 3        9 8 7
1 2        2 1 6
           3 4 5

Требуется по данному размеру матрицы n и номеру r вывести r-ю строку матрицы.

Формат входного файла:
Входной файл содержит натуральные числа n и r.

Формат выходного файла:
Выходной файл должен содержать n чисел — r-ю строку матрицы.

Ограничения:
1<r<n<10^5

Примеры тестов №    Входной файл    Выходной файл
           1          2 1            4 3
           2          3 2            2 1 6
           3          4 3            6 1 2 11

Дело в том,что программу я написал.Только на Time limit exceeded on test 26.
Подскажите программеры всего мира как сгенерировать только одну строку каким-либо эффективным алгоритмом,чтобы и памяти мало занимало и выполнядось за 1 секунду.
Вот код Delphi:

Код


program spiral;

{$APPTYPE CONSOLE}

uses
  SysUtils;
{$apptype console}

type
 MyArray=array of Int64;

var
  a:MyArray;
  i,j,c,r:integer;
  t1,t2:text;
  n,t:int64;

begin
 assign(t1,'input.txt'); reset(t1);
 assign(t2,'output.txt'); rewrite(t2);


  read(t1,n,r);
 SetLength(a,n);
  //for i:=0 to n-1 do
   //SetLength(a[i],n);


   i := 1;
   j := 1;
   c := 0;
   t := n*n;

   repeat

       while (j <= n - c) do
       begin
       if (i=r) then
        A[j-1] := t;
       inc(j); dec(t); end;
       inc(i); dec(j);

       while (i <= n - c) do
       begin
       if (i=r) then
        A[j-1] := t;
       inc(i); dec(t); end;
       dec(j); dec(i);

       while (j >= 1 + c) do
       begin
       if (i=r) then
        A[j-1] := t;
       dec(j); dec(t); end;
       inc©; inc(j); dec(i);

       while (i >= 1 + c) do
       begin
        if (i=r) then
         A[j-1] := t;
       dec(i); dec(t);
       end;
       inc(j); inc(i);

   until c > n div 2;


 for j:=0 to n-1 do
     write(t2,a[j],' ');

close(t1);
close(t2);

end.

P.S. Буду весьма признателен.Эту задачу я долго мучал,но никак не могу добиться окончательного эффективного решения.
e-mail
Модератор: пользуемся кнопкой "Код"