Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Художник

(Время: 1 сек. Память: 16 Мб Сложность: 31%)
Художник

В этой задаче необходимо понять, что координаты закрашиваемых прямоугольников определяются не координатами ячеек, а координатами сетки, т.е. левая верхняя координата имеет значение (0,0) в то время как правая нижняя - (w,h). Это следует из примеров, первый из которых представлен на рисунке справа, где видно, что действительно 18 клеток таблицы не закрашены.

Данная задача решается "в лоб". Можно определить матрицу a[1..n][1..m] и пошагово считывать координаты противоположных вершин прямоугольника и сразу же заполнять единицами этот прямоугольник в матрице. Предварительно матрицу необходимо обнулить. По завершении процесса можно подсчитать число оставшихся нулей в матрице, это и будет ответом на задачу. Максимальное число простых операций может быть равно 50 000 000. Несмотря на такое, казалось бы огромное число решение задачи укладывается в 1 секунду. Дело в том, что проводимые операции - это заполнение элеметов массива числами, которые выполняются очень быстро. Если бы столько же раз нам нужно было выполнить серию умножений, то мы вряд ли смогли бы рассчитывать на успех.

Приведем пример решения данной задачи на алгоритмическом языке:

  int a[1..100][1..100]={0...0};

  read(w,h,n);
  for i=1..n{
    read(x1,y1,x2,y2);
    for y=y1+1..y2{
      for x=x1+1..x2{
        a[y][x]=1;
      }
    }
  }
  c=0;
  for y=1..h{
    for x=1..w{ 
      c=c+1-a[y][x];
    }
  }
  write(c);

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483