Квадраты

Районная олимпиада школьников Удмуртии по программированию, 1995 год

Прямоугольник размером H на W расчертили на клеточки с шагом 1 (т.е. на HW клеточек). Теперь на этом прямоугольнике можно заметить, что обведено много разных квадратов разного размера (1×1, 2×2, …).

Задача, по заданным H и W подсчитать общее количество всевозможных квадратов.

Пример

На входе:
H=2
W=4
На выходе:
11

Решением задачи будет таблица вида:

       1  4  7 10 13 16 19 22 25 28
    1  1  .  .  .  .  .  .  .  .  .
    2  . 11  .  .  .  .  .  .  .  .
    4  .  .  .  .  .  .  .  .  .  .
    8  .  .  .  .  .  .  .  .  .  .
   16  .  .  .  .  .  .  .  .  .  .
   32  .  .  .  .  .  .  .  .  .  .
   64  .  .  .  .  .  .  .  .  .  .
  128  .  .  .  .  .  .  .  .  .  .
  256  .  .  .  .  .  .  .  .  .  .
  512  .  .  .  .  .  .  .  .  .  .

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

Время работы программы 1 секунда

Добавить комментарий