前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >棋盘(数学趣味题) - HDU 5100

棋盘(数学趣味题) - HDU 5100

作者头像
ACM算法日常
发布2018-08-07 17:14:43
6300
发布2018-08-07 17:14:43
举报
文章被收录于专栏:ACM算法日常

Problem Description

Consider the problem of tiling an n×n chessboard by polyomino pieces that are k×1 in size; Every one of the k pieces of each polyomino tile must align exactly with one of the chessboard squares. Your task is to figure out the maximum number of chessboard squares tiled.

对于一个n*n大小的棋盘,放入k*1大小的长方形,放入后需要对齐(也就是说不考虑浮点型位置)。

求能放入的最大面积。

Input

There are multiple test cases in the input file.

First line contain the number of cases T (T≤10000).

In the next T lines contain T cases , Each case has two integers n and k. (1≤n,k≤100)

输入T,表示有T个用例

每个用例输入棋盘大小n和长方形的长k。

Output

Print the maximum number of chessboard squares tiled.

Sample Input

2

6 3

5 3

Sample Output

36

24

这是一个数学题,对于每个k,有两种不同的放置方法。

  1. 先横着摆放,然后用竖着的补全,剩下的是一个边长为n%k的正方形
  2. 在一个角摆成风车形(边长k+n%k),中间形成边长为k-n%k的正方形

(方法1 先横着后竖着)

(方法2 摆成风车型)

比如对于5和3来说,如果采用方法1,那么剩下的方形边长是2,采用方法2,剩下的方形边长是1。

源代码:G++ 0ms

代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int test_count;
    scanf("%d", &test_count);

    while (test_count--)
    {
        int n, k;
        scanf("%d%d", &n, &k);

        if (k > n)
            puts("0");
        else {
            if (n % k == 0)
                printf("%d\n", n * n);
            else {
                //两种摆法取边小的
                //1、横着摆放竖着补全,形成边长n%k的正方形 
                //2、在一个角摆成风车形(边长k+n%k),中间形成边长为k-n%k的正方形
                int m = min(n % k, k - n % k);
                printf("%d\n", n * n - m*m);
            }
        }
    }
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-05-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档