Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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);

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ