Геометрическая задача

[Poma][a]

Утро Доброе
Вчера на информатике, когда весь класс проходил Write, мне дали решать задачки на различные темы. И если с простыми числами-близнецами, с совершенными числами, etc я справился в легкую, одно ужасно простая задача выбила меня из рабочей калии.

Собственно задача : Есть пол, размером N на M. И есть квадратики со стороной K. Каким наименьшим кол-вом квадратиков можно покрыть пол?

Сначала я пытался нахимичить с DIV и MOD. Затем я решил, поняв что времени у меня мало, и вывести обобщенную формулу у меня не получится, я загнал всё в матрицу. В состоянии аффекта, задачу я не решил, придя же домой нашел у себя ошибку.. Программа, вроде, работает, но решать относительно простую задачу с помощью двух мерных массивов - перебор!
Поэтому не подскажете ли Вы более красивое решение ?

Мое решение :

var
    a : array [1..100, 1..100] of Integer;
    n, m, k, count, i, j, i1, j1 : Integer;

begin
    Read (n, m, k);

    for i := 1 to n do
        for j := 1 to m do
            a[i, j] := 1;


    count := 0;

    for i := 1 to n do
        for j := 1 to m do

            if a[i, j] = 1 then begin
                Inc(count);
                for i1 := i to i+k-1 do
                    for j1 := j to j+k-1 do
                        a[i1, j1] := 0

            end;

    WriteLn (count)
end.

[Sciv]

из рабочей калии.

Калия - это производная от какого слова?

Общую площадь на площадь квадрата делить не пробовал?

y=(n*m) div (k*k);

Вопрос возникает - можно ли эту плитку резать, чтоб замостить остальное? Или использовать только целые квадраты?

[DiemonStar]

Вопрос возникает - можно ли эту плитку резать, чтоб замостить остальное? Или использовать только целые квадраты?

с целыми тоже не столь сложно:

y := (n div k + (n mod k > 0)) * (m div k + (m mod k > 0));

[Serge_Bliznykov]

думаю, что некоторые квадраты можно класть друг на друга "в нахлёст" (иначе задачу невозможно решить, например, для пола размером 5 x 5 и плиткой K=3

если покрытие допускается, тогда всё просто:

var
  N, M, K : integer;
  Kvadrtov_po_n,   Kvadrtov_po_m : integer;
begin
  Readln(N, M, K);
  Kvadrtov_po_n := n div K + ord((n mod K) <> 0);
  Kvadrtov_po_m := m div K + ord((m mod K) <> 0);

  WriteLn('Kolichesto plitok = ',Kvadrtov_po_n*Kvadrtov_po_m);
  Readln
end.

Всё настолько просто, что мне кажется, что я чего-то не учёл!


p.s. ну и разумеется, если плитку можно (нужно) резать - тогда это решение не подходит! Но об этом же должно быть сказано в условии!

[Sciv]

Всё настолько просто, что мне кажется, что я чего-то не учёл!

Так ведь задача-то для школьников

[Smitt&Wesson]

В условии всё предельно ясно сказано:

Каким наименьшим кол-вом квадратиков можно покрыть пол?

DiemonStar, уже дал ответ. Для усложнения решения, я бы сформулировал задачу так: Можно-ли выложить пол, размерами N на M, квадратиками, со стороной K, чтобы зазор между ними не превышал 1/10 K, со всех сторон? По моему, в таком виде, задачка выглядела-бы более привлекательно.

[s-andriano]

Вообще-то здесь просто нужна функция, округляющая по избытку. В математической библиотеке Паскаля такая может быть под названием Ceil.
В целых числах вместо

n div K + ord((n mod K) <> 0)

может быть записано

(n + K - 1) div K

А если у нас размеры заданы в числах вещественных, то вместо 1 следует
взять eps, где eps > 0 - малая величина. Ну и дополнить преобразованием типа

trunc((n + K - eps)/K)

Кстати, у eps может быть и физический смысл, например - максимально допустимая ширина щели.

[Poma][a]

Калия - это производная от какого слова?

Ранним утром, перед школой, после бессонной ночи и не такое напишешь

Вопрос возникает - можно ли эту плитку резать, чтоб замостить остальное? Или использовать только целые квадраты?

Только целые

думаю, что некоторые квадраты можно класть друг на друга "в нахлёст" (иначе задачу невозможно решить, например, для пола размером 5 x 5 и плиткой K=3

Именно

y := (n div k + (n mod k > 0)) * (m div k + (m mod k > 0));

Гениально!! Конечно же! Сначала берем целую далее добавляем!

Всё настолько просто, что мне кажется, что я чего-то не учёл!

Пойду от стыда тереть своё первоначально решение

Огромное спасибо!!