Задача
Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”
Входные данные
В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.
Выходные данные
Для каждого примера, заданного Печкиным, выведите в отдельной строке через пробел искомые количества сначала квадратных, а потом прямоугольных досок.
Тесты
| № | Входные данные | Выходные данные |
| 1. | 1 3 2 |
8 10 |
| 2. | 2 4 4 2 2 |
30 70 5 4 |
| 3. | 4 3 3 25 46 100 100 1 1 |
14 22 12350 338975 338350 25164150 1 0 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class Main { public static void main(String[] args) { java.util.Scanner jin = new java.util.Scanner(System.in); int k; // Количество заданий k = jin.nextInt(); for(int l = 0; l = 0; i--) // Находим количество квадратов { res += (m - i) * (n - i); } System.out.print(res); // Вывод количества квадратных досок res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников { for(int j = n - 1; j >= 0; j--) { res += (m - i) * (n - j); } } System.out.println(" " + res); // Вывод количества прямоугольников } // write your code here } } |
Объяснение
Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.
Пояснение к первому тесту
Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.
Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.
Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.
Ссылки
Условие на e-olymp.
Код на ideone.