Задачи на перестановки Опции

[Unconnected]

Привет всем.

Меня заинтересовала задача из соседней темы, про перестановки в числах.

Задача 4 "Сумма двух чисел"
Имя входного файла: sum.in
Имя выходного файла: sum.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

Формат входных данных
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.

Формат выходных данных
Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.
Примеры входных и выходных файлов
sum.in sum.out
12 31 25 ***YES***
**********12 13***


12 31 26 ***NO***

Вот что я сделал:

const m=6;

type st = string[3];

var a,b:st;
    m1,m2:array[1..m] of st;
    f:text;
    i,j:byte;
    buf1,buf2,c,code,aa,bb:integer;

Procedure generate(m:array of st;v:st);
var buf:char;
    i:byte;
begin
  if (length(v)<3) then repeat v:=v+'0' until (length(v)=3);
  i:=1;
  m[i]:=v;
  repeat
    inc(i);
    m[i][1]:=m[i-1][2];
    m[i][2]:=m[i-1][3];
    m[i][3]:=m[i-1][1];
  until (i=3);
  inc(i);
  m[i][1]:=m[1][1];
  m[i][2]:=m[1][3];
  m[i][3]:=m[1][2];
  repeat
    inc(i);
    m[i][1]:=m[i-1][2];
    m[i][2]:=m[i-1][3];
    m[i][3]:=m[i-1][1];;
  until (i=6);
end;

begin
  assign(f,'sum.in');
  reset(f);
  read(f,aa,bb,c);
  close(f);
  str(aa,a);
  str(bb,b);
  generate(m1,a);
  generate(m2,b);
  for i:=1 to m do
    begin
      val(m1[i],buf1,code);
      for j:=1 to m do
        begin
          val(m2[j],buf2,code);
          if (buf1+buf2=c) then begin
                                  assign(f,'sum.out');
                                  rewrite(f);
                                  writeln(f,'YES');
                                  write(buf1,' ',buf2,' ',c);
                                  close(f);
                                  halt;
                                end;
        end;
    end;
  readln;
  assign(f,'sum.out');
  rewrite(f);
  write(f,'NO');
  close(f);
end.

Мой алгоритм перестановок (для трёхзначных чисел) основан на том, что если в числе переносить первую цифру в конец, пока не получится исходное число, а потом поменять 2 и 3 цифры местами и сделать то же самое, то получатся все перестановки..

Например:
123
231
312
меняем,
132
321
213

Получилось 6 перестановок, как раз 3!, как и должно быть. Моя программа почему-то не заполняет корректно массив (процедура Generate).

Сообщение отредактировано: Unconnected - 18.01.2010 13:21

[Lapp]

А я уже говорил, что надо бы описывать тип
...
Посмотрим, получится ли у тебя его убедить...

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

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

Да, то, что лидирующие нули не нужно учитывать, довольно сильно меняет ситуацию. Я рыпнулся было делать перестановки, но быстро остыл и переключился на рекурсию. Не хочу сказать, что это невозможно или намного труднее, но все же требует внимательности в разработке алгоритма. А рекурсия - дубовый метод, много мозгов не требует )). Тут, правда, осложнение в том, что переставляемая строка разбита на участки (числа); это потребовало передачи двух параметров в рекурсивную процедуру. А тем более, начальные условия такие щадящие. [прошло полчаса] Ха, интересно! Я думал, что увеличение количества чисел резко замедлит работу программы. Но..
Например, вот такие входные данные:

1372 62 552 381 6924 91 1583 4973 21 8119 30504

(при m=10, разумеется) легко выдают ответ:

YES
1372 62 552 381 6924 91 1853 9437 21 9811 

- и увеличения времени на глаз не заметно! А штука в том, что.. Unconnected, сможешь ответить, почему?