You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:
1. Each domino completely covers two squares.
2. No two dominoes overlap.
3. Each domino lies entirely inside the board. It is allowed to touch the edges of the board.
Find the maximum number of dominoes, which can be placed under these restrictions.
Input
In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).
Output
Output one number — the maximal number of dominoes, which can be placed.
Examples
Input
2 4
Output
4
Input
3 3
Output
4
Solution
Consider the following scenarios:
If both M and N are even, each 2 x 1 domino tile can perfectly cover 2 squares without any leftover squares, so you can directly divide by 2.
If either M or N is odd, you can place a 2 x 1 domino tile in one direction to cover the odd rows or columns, and the remaining squares will still be in even rows or columns, which can be handled by the method mentioned above, directly dividing by 2.
In summary, regardless of whether M and N are even or odd, each 2 x 1 domino tile can ensure the coverage of 2 squares, so you can directly divide by 2 to calculate the maximum number of dominoes without encountering any mismatched situations. This is because the shape of the domino tiles is compatible with the arrangement of the squares.
C# Solution
Solution1
string[]arr = Console.ReadLine().Split(' '); //split by space
int m = int.Parse(arr[0]);
int n = int.Parse(arr[1]);
Console.WriteLine(m*n/2);
Java Solution
Solution1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] arr = scanner.nextLine().split(" ");
int m = Integer.parseInt(arr[0]);
int n = Integer.parseInt(arr[1]);
System.out.println(m*n/2);
}
}
Python3 Solution
Solution1
arr = input().split(' ')
m = int(arr[0])
n = int(arr[1])
print(int(m*n/2))
Python divide operator (/) will always return a float number, providing a decimal result.
However, if you need an integer result, you should use the floor division operator (//). The floor division ensures that the result is rounded down to the nearest integer.
JavaScript Solution
Solution1
var arr = readline().split(' ');
var m = parseInt(arr[0]);
var n = parseInt(arr[1]);
print(Math.floor(m*n/2));
Similar to Python, we need to ensure that we don’t end up with a floating-point number when performing the calculation.
Conclusion
🧡If my solution helps, that is my honor!
🧡You can support me by sharing my posts or clicking ads, thanks you~~
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"cc175a72d9"};
var uagb_data = {"ajax_url":"https:\/\/zyrastory.com\/wp-admin\/admin-ajax.php","uagb_masonry_ajax_nonce":"cc175a72d9","uagb_grid_ajax_nonce":"7cac865027"};
( function() {
let elements = document.querySelectorAll( '.uagb-post-grid.uagb-block-613bccac .uagb-post-pagination-wrap a' );
elements.forEach(function(element) {
element.addEventListener("click", function(event){
event.preventDefault();
const link = event.target.getAttribute('href').match( /\/page\/\d+\// )?.[0] || '';
const regex = /\d+/; // regular expression to match a number at the end of the string
const match = link.match( regex ) ? link.match( regex )[0] : 1; // match the regular expression with the link
const pageNumber = parseInt( match ); // extract the number and parse it to an integer
window.UAGBPostGrid._callAjax({"btnBorderStyle":"none","overallBorderColor":"","block_id":"613bccac","categories":"269","displayPostExcerpt":false,"displayPostComment":false,"displayPostImage":false,"imgSize":"medium","linkBox":false,"orderBy":"rand","excludeCurrentPost":true,"postPagination":true,"pageLimit":0,"imageRatio":"2-3","imgEqualHeight":true,"btnBorderLink":true,"btnBorderRadiusLink":true,"overallBorderLink":true,"overallBorderRadiusLink":true,"inheritFromTheme":true,"postType":"post","postDisplaytext":"No post found!","taxonomyType":"category","postsToShow":6,"enableOffset":false,"postsOffset":0,"displayPostDate":true,"excerptLength":15,"displayPostAuthor":false,"displayPostTitle":true,"displayPostTaxonomy":false,"hideTaxonomyIcon":true,"taxStyle":"default","displayPostTaxonomyAboveTitle":"withMeta","imgPosition":"top","bgOverlayColor":"#000000","overlayOpacity":"50","displayPostLink":true,"newTab":false,"ctaText":"Read More","inheritFromThemeBtn":false,"buttonType":"primary","btnHPadding":"","btnVPadding":"","columns":3,"tcolumns":2,"mcolumns":1,"align":"left","width":"wide","order":"desc","rowGap":20,"rowGapTablet":20,"rowGapMobile":20,"columnGap":20,"bgType":"color","bgColor":"#f6f6f6","titleTag":"h4","titleFontSize":"","titleFontSizeType":"px","titleFontFamily":"","titleLineHeightType":"em","titleLoadGoogleFonts":false,"metaColor":"","highlightedTextColor":"#fff","highlightedTextBgColor":"#3182ce","metaFontSize":"","metaFontSizeType":"px","metaFontFamily":"","metaLineHeightType":"em","metaLoadGoogleFonts":false,"excerptColor":"","excerptFontSize":"","excerptFontSizeType":"px","excerptFontFamily":"","excerptLineHeightType":"em","excerptLoadGoogleFonts":false,"displayPostContentRadio":"excerpt","ctaBgType":"color","ctaBgHType":"color","ctaFontSize":"","ctaFontSizeType":"px","ctaFontFamily":"","ctaLineHeightType":"em","ctaLoadGoogleFonts":false,"paddingTop":20,"paddingBottom":20,"paddingRight":20,"paddingLeft":20,"contentPadding":20,"ctaBottomSpace":0,"ctaBottomSpaceTablet":0,"ctaBottomSpaceMobile":0,"imageBottomSpace":15,"titleBottomSpace":15,"metaBottomSpace":15,"excerptBottomSpace":25,"contentPaddingUnit":"px","rowGapUnit":"px","columnGapUnit":"px","excerptBottomSpaceUnit":"px","paginationSpacingUnit":"px","imageBottomSpaceUnit":"px","titleBottomSpaceUnit":"px","metaBottomSpaceUnit":"px","ctaBottomSpaceUnit":"px","paddingBtnUnit":"px","mobilePaddingBtnUnit":"px","tabletPaddingBtnUnit":"px","paddingUnit":"px","mobilePaddingUnit":"px","tabletPaddingUnit":"px","isPreview":false,"taxDivider":", ","titleLetterSpacing":"","titleLetterSpacingType":"px","metaLetterSpacing":"","metaLetterSpacingType":"px","ctaLetterSpacing":"","ctaLetterSpacingType":"px","excerptLetterSpacing":"","excerptLetterSpacingType":"px","useSeparateBoxShadows":true,"boxShadowColor":"#00000070","boxShadowHOffset":0,"boxShadowVOffset":0,"boxShadowBlur":"","boxShadowSpread":"","boxShadowPosition":"outset","boxShadowColorHover":"","boxShadowHOffsetHover":0,"boxShadowVOffsetHover":0,"boxShadowBlurHover":"","boxShadowSpreadHover":"","boxShadowPositionHover":"outset","borderWidth":"","borderStyle":"none","borderColor":"","borderRadius":"","blockName":"post-grid","equalHeight":true,"paginationBgActiveColor":"#e4e4e4","paginationActiveColor":"#333333","paginationBgColor":"#e4e4e4","paginationColor":"#777777","paginationMarkup":"","paginationLayout":"filled","paginationBorderColor":"#888686","paginationBorderSize":1,"paginationSpacing":20,"paginationAlignment":"left","paginationPrevText":"\u00ab Previous","paginationNextText":"Next \u00bb","layoutConfig":[["uagb\/post-image"],["uagb\/post-taxonomy"],["uagb\/post-title"],["uagb\/post-meta"],["uagb\/post-excerpt"],["uagb\/post-button"]],"post_type":"grid","equalHeightInlineButtons":false,"paginationType":"ajax","isLeftToRightLayout":false,"wrapperTopPadding":"","wrapperRightPadding":"","wrapperLeftPadding":"","wrapperBottomPadding":"","wrapperTopPaddingTablet":"","wrapperRightPaddingTablet":"","wrapperLeftPaddingTablet":"","wrapperBottomPaddingTablet":"","wrapperTopPaddingMobile":"","wrapperRightPaddingMobile":"","wrapperLeftPaddingMobile":"","wrapperBottomPaddingMobile":"","wrapperPaddingUnit":"px","wrapperPaddingUnitTablet":"px","wrapperPaddingUnitMobile":"px","wrapperPaddingLink":false,"wrapperAlign":"row","wrapperAlignPosition":"center","extended_widget_opts_block":{},"extended_widget_opts":{},"extended_widget_opts_state":"","extended_widget_opts_clientid":"","dateUpdated":""}, pageNumber, '613bccac');
});
});
} )();
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};