Написать программу для решения на любом из яп
на одном из скучнейших уроков максим решил развлечь себя следующим странным он взял прямоугольный лист клетчатой бумаги размером n на m клеток и выбрал какие-то k из них. затем, для каждой выбранной клетки максим полностью закрасил столбец и строку, в которых эта клетка находится. в результате, на листе осталось несколько незакрашенных прямоугольных областей.
теперь максим хочет узнать количество таких областей, но, так как лист большой, ему нужна ваша .
формат файла входных данных:
в первой строке даны три числа n, m, и k – количество строк и столбцов в листе и количество выбранных клеток (1 ≤ n, m ≤ 104, 0 ≤ k ≤ 100). в следующих k строках даны два числа ri и ci – строка и столбец, в которых находится очередная выбранная клетка (1 ≤ ri ≤ n, 1 ≤ ci ≤ m). гарантируется, что каждая выбранная клетка встречается в списке только один раз.
формат файла выходных данных:
выведите одно число – количество незакрашенных прямоугольных областей.
система оценки:
правильные решения для n, m ≤ 10 оцениваются из 30 .
правильные решения для n, m ≤ 1000 оцениваются из 50 .
20
= 2 + 4 = 6
Отрицательное число представляется в дополнительном коде, т.е. нули заменяются единицами (и единицы - нулями), а потом в младшем разряде к полученному числу прибавляется единица.
Вначале перевод.
-13(10)=-0001101(2)
Инвертируем биты: 1110010
Прибавляем единицу: 1110011
И дописываем слева 1 в качестве знака. 1 1110011
Аналогичным образом поступаем и с числом -7:
-7(10)=-0000111(2)
Инвертируем биты: 1111000
Прибавляем единицу: 1111001
И дописываем слева 1 в качестве знака. 1 1111001
Теперь сложение. Выполняем его в столбик для всех восьми бит.
11110011
+ 11111001
11101100
У нас при сложении появилась единица переноса из левого разряда, но дальше уже разрядов нет и она просто отбрасывается.
Результат получился с единичным знаковым разрядом. Поэтому для получения величины результата поступаем в обратном порядке: отделяем семь правых бит, вычитаем единицу и снова инвертируем полученное значение. Вместо единичного знакового разряда приписываем числу знак минус.
1101100 - 1 = 1101011. Инверсия: 0010100, результат -10100(2)=-20(10)