Массивы, задачка... I need help ! Опции

[Valkirie]

Ребята, помогите, плииз.... чё то я не совсем понимаю...что тут к чему...

Вводится прямоугольный массив, состоящий из 0 и 1. Можно ли в нем выбрать 2 строки так, чтобы в них каждый столбец содержал хотя бы одну единицу. Динамическими массивами не пользоваться.

Вход
В первой строке входа дано количество строк M и количество столбцов N в массиве. Далее следуют MxN элементов массива в следующем порядке: сначала элементы первой строки, затем элементы второй строки и т.д. (0 либо 1, по одному в каждой строке).

Выход
На выход напечатать yes в случае положительного ответа и no в случае отрицательного.

[hiv]

Что-то тут условие не полное... Наверно массив состоит из чисел содержащих цифры 0 и 1.

[volvo]

Динамическими массивами не пользоваться.

Условие совершенно излишнее... Во-первых, в TP просто нет динамических массивов, ну а во-вторых, здесь ВООБЩЕ никакие массивы не нужны. Все, что нужно - прочесть 2 значения (M и N), и сделать 2 вложенных цикла (проверяя, есть ли в M-ой "строке" хотя бы одна единица. Если есть - то увеличить счетчик). Ну а потом - просто проверить, содержится ли в счетчике число >= 2 ...

[hiv]

Volvo, прочти еще раз что было написано:

чтобы в них каждый столбец содержал хотя бы одну единицу

я так это понял - что в каждом элементе строки массива должна быть минимум одна еденица.

[volvo]

Очень интересно... Задачка стоит в теме "Двумерные массивы", но динамическими массивами не пользоваться ...
Задача 8018

[Valkirie]

Угу..вот такой вот попандос....
ладно, спасибо ребят..
попробую что-нить сделать

[volvo]

Valkirie, ну нельзя динамическими, пользуйся статическим... Например, объяви массив мз 100 LongInt-ов (назовем его Arr) и считай каждую "строку" матрицы двоичным представлением числа. Загоняешь эти самые "строки" в массив LongInt-ов и потом перебором:

Код

if (Arr[i] or Arr[j]) = ($FFFFFFFF shr (32-N)) then { такая пара "строк" содержит 1-цы в каждом столбце }

Естественно, это накладывает ограничения на число столбцов матрицы: оно не должно быть больше 32.

[Valkirie]

:p2: чего-то у меня с головой наверное не то...
т.е. если массив прямоугольный - то он многомерный...или нет...
мне его как объявлять...?
так ?

Код

const maxN=32;
 maxM=32;
var Arr:array [1..maxM] of array [1..maxN] of integer;

но тогда с условием лажа получается...

блин этот универ, вечно нифига не объяснят - и решайте... <_<

[klem4]

Объявление двумерного массива (прямоугольной матрицы)

Код

const n=5;
       m=4;
var
x:array[1..n,1..m] of integer;

Сообщение отредактировано: klem4 - 18.03.2005 0:54

[volvo]

Ну зачем же так круто? Оба измерения - не надо
Достаточно одного... Смотри:

Код

Const maxN = 32;
Var Arr: array[1 .. 100] of LongInt;
begin
 { Читаем M, N }
 for i := 1 to m do
   for j := 1 to n do
     begin
       readln(x); { Читаем очередное число }
       if x = 1 then Arr[i] := Arr[i] or $1;
       Arr[i] := Arr[i] shl 1
     end;
 { Заполнила массив чисел, теперь - перебором их... }
end.

[Valkirie]

Код

const maxN=32;
 maxM=32;
var Arr:array [1..maxM, 1..maxN] of integer;
N, M, i, j: integer;
begin
Write('');
ReadLn(M,N);
for i:=1 to M do
for j:=1 to N do
begin
Write('');
ReadLn(Arr[i,j]);
end;
if (Arr[i,j] or Arr[j,i]) = ($FFFFFFFF shr (32-N)) then
begin
WriteLn('yes');
ReadLn;
end
else
WriteLn('no');
ReadLn

end.

я наверное дура полная...
Так прога работает...и всё правильно выдаёт...
А этот сервер пишет - что всё не правильно...

volvo, сщас буду пробовать воспользоваться твоим последним советом...
Пасиб :p2:

[klem4]

мне кажется это

Код

if (Arr[i,j] or Arr[j,i]) = ($FFFFFFFF shr (32-N)) then

должно быть в цикле...

[Valkirie]

Если бы я ещё понимала, чего от меня хотят.... было-бы вообще хорошо...

[volvo]

Если бы я ещё понимала, чего от меня хотят...

Допустим, у тебя есть матрица:
0 0 0 1 1 0
0 1 1 1 1 0
1 1 1 1 0 0
Это должно выдать "нет" потому что нет в 6-ой позиции единицы нигде...
В общем случае - надо как бы "складывать" строки: "0" + "0" = "0", все остальные комбинации = "1", и смотреть, есть ли 2 строки, при "сложении" которых получаются ВСЕ единицы...

Добавлено позже:
Я вот тут подумал, а нужно ли заморачиваться с LongInt-ами? Можно ведь сделать еще проще (тут число столбцов ограничено не 32, как с LongInt-ами, а 255):

Код

Type TSet = Set Of Byte;
Var
 Arr: array[1 .. 100] of TSet;
 i, j, m, n, x: integer;
begin
{ Читаем M, N }
for i := 1 to m do
  begin
    Arr[i] := [];
    for j := 1 to n do
      begin
        readln(x); { Читаем очередное число }

        { в список заносим только столбцы содержащие 1-цы }
        if x = 1 then Arr[i] := Arr[i] + [j];
      end;
  end;
{ Заполнила массив множеств, теперь - перебор... }
for i := 1 to m-1 do
  for j := i+1 to m do
    { проверка, все ли столбцы находятся в объединенном списке строк i и j? }
    if Arr[i] + Arr[j] = [1 .. n] then
      writeln('строки ', i, ' и ', j, 'содержат 1-цы во всех столбцах')
end.