HBC202138Mr. Panda and Dominoes题解

爱的那么颓废 算法基础篇 164 0
不断提升技能,才能在职场中立于不败之地!全网最全C++题库,助您成为编程领域的佼佼者。
Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle when he was playing dominoes.In a grid that consists of an infinite number of rows and columns, all

Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle when he was playing dominoes.In a grid that consists of an infinite number of rows and columns, all cells are white except Nmathbf{N}N given cells which are colored black. Mr. Panda wants to know how many dominoes there are in the gird.A domino is a rectangle that meets the following requirements. The domino is formed of a continuous subset of the rows and columns of the grid. The domino has at least 1{1}1 row and 1{1}1 column. The cells on the edge of the domino are black. It means the topmost row, the bottommost row, the leftmost column and the rightmost column only consist of black cells. The aspect ratio of the domino is 2:1{2:1}2:1 or 1:2{1:2}1:2. It means, if the domino has k{k}k columns, it should have either 2k{2k}2k rows or k2frac{k}{2}2k​ rows (k{k}k is an even number in this case). For example, in the chart below, the 3×33 times 33×3 grid on the left contains 6{6}6 dominos (4{4}4 dominos of 1×21 times 21×2 and 2{2}2 dominos of 2×12 times 12×1), and the 3×63 times 63×6 grid on the right contains 15{15}15 dominos (10{10}10 dominos of 1×21 times 21×2, 4 dominos of 2×12 times 12×1 and a domino of 3×63 times 63×6). Because the grid is huge, Mr. Panda is too lazy to count the number of dominoes. Could you please help Mr. Panda find how many dominoes there are in the gird?

HBC202138Mr. Panda and Dominoes题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断挑战自我,才能突破极限!全网最全C++题库,让您在编程道路上越走越远。

标签: HBC202138Mr. Panda and Dominoes题解