Хитрое заполнение ячеек Опции

[Unconnected]

Привет всем.

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

Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.
Во входном файле записаны три числа – N, K, S (1 ≤ N ≤ 100, 1 ≤ K ≤ N, 0 ≤ S ≤ K2).

И вывести надо получившуюся матрицу. Может кто-нибудь объяснить алгоритм решения? Я додумался лишь до того, что сначала надо посчитать все возможные "квадраты", а уже потом, исходя из их расположения заполнять..

[volvo]

Если ты возьмешь и заполнишь квадрат K*K нужным количеством единиц, а потом этим квадратом заполнишь большой квадрат N*N - то твоя задача будет решена, в любом квадрате K*K внутри большого квадрата сумма единиц будет одинакова. Почему так - разберешься?

P.S. Заполнять квадрат N*N - "насколько хватит". Если N на K не делится нацело, и остался один свободный столбец - то заполнить этот столбец первым столбцом малого квадрата. То же самое - со строками.

[Unconnected]

Если ты возьмешь и заполнишь квадрат K*K нужным количеством единиц, а потом этим квадратом заполнишь большой квадрат N*N - то твоя задача будет решена, в любом квадрате K*K внутри большого квадрата сумма единиц будет одинакова. Почему так - разберешься?

P.S. Заполнять квадрат N*N - "насколько хватит". Если N на K не делится нацело, и остался один свободный столбец - то заполнить этот столбец первым столбцом малого квадрата. То же самое - со строками.

Мысль понял, провел эксперимент - действительно условие выполняется... Буду воплощать в код, спасибо:)

[Unconnected]

Решил, ( ), вот, если кому интересно:

uses sysutils;
var f:textfile;
    n,k,i,j,x,y:byte;
    s:integer;
    big,small:array[1..100,1..100] of char;
begin
  assignfile(f,'input.txt');
  reset(f);
  read(f,n,k,s);
  closefile(f);
  for i:=1 to n do
    for j:=1 to n do big[i,j]:='0';
  x:=0;
  for i:=1 to k do
    for j:=1 to k do
      begin
        if (x=s) then break;
        inc(x);
        small[i,j]:='1';
      end;
  for i:=1 to k do
    for j:=1 to k do if small[i,j]<>'1' then small[i,j]:='0';
  x:=0;
  y:=0;
  for i:=1 to n do
    begin
      if (y=k) then y:=1 else inc(y);
      for j:=1 to n do
        begin
          if (x=k) then x:=1 else inc(x);
          big[i,j]:=small[x,y];
        end;
     end;
  assignfile(f,'output.txt');
  rewrite(f);
  for i:=1 to n do
    begin
      for j:=1 to n do write(f,big[i,j],' ');
      writeln(f);
    end;
  closefile(f);
end.

Хотел правда массивы динамическими сделать, но я не знаю, как для многомерных память выделять.

Сообщение отредактировано: Unconnected - 29.10.2009 16:57

[volvo]

я не знаю, как для многомерных память выделять.

Вот так: Динамические массивы и матрицы

[Unconnected]

volvo, а как по-твоему, само решение верное? Будет ли отрабатывать на больших массивах?

[volvo]

Должно работать на любых матрицах. Хотя не совсем понятно:
1) зачем ты заполняешь элементы массива посимвольно, если есть FillChar:

//  for i:=1 to n do
//    for j:=1 to n do big[i,j]:='0';
FillChar(big, sizeof(big), '0');

Точно так же сначала заполнить small нулями, а потом, где надо, поставить единицы, избавишься от вложенного цикла.

2) У тебя матрица big заполняется НЕ "образцом" из small. Распечатай small и убедись в этом. Потому что надо так:

  y:=0;
  for i:=1 to n do
    begin
      if (y=k) then y:=1 else inc(y);
      x := 0; // Вот тут обнуляем X
      for j:=1 to n do
        begin
          if (x=k) then x:=1 else inc(x);
          big[i,j]:=small[y, x]; // А тут - меняем индексы местами
        end;
     end;

Вот тогда будет точное заполнение. Здесь это не играет особой роли, но на будущее - внимательнее с такими вещами, где-нибудь может вылезти неправильное поведение. Можно попробовать похимичить с MOD и обойтись без доп. переменных X, Y.

[Unconnected]

Спасибо, учту..