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

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

#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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏眯眯眼猫头鹰的小树杈

leetcode337. House Robber III

最开始的思路我是采用自顶向下递归遍历树的形式来计算可能获得的最大收益。当前节点的情况有两种:选中或是没选中,如果选中的话,那么两个直接子节点将不可以被选中,如果...

1163
来自专栏令仔很忙

限制字符串输入——正则表达式(VB.NET)

在做机房收费系统的时候,几乎所有的窗体上都存在着文本框或者组合框,当用户进行操作的时候,首先要判断是否为空,然后再对各种属性进行判断,比如;卡号、学号、金额等...

3021
来自专栏coder修行路

Go 处理yaml类型的配置文件

6544
来自专栏Java帮帮-微信公众号-技术文章全总结

【大牛经验】26种语言输出HelloWord

【大牛】26种语言输出HelloWord 1. C ? ---- 2. C++ ? ---- 3. C# ? ---- 4. Bash echo "Hello,...

3968
来自专栏coder修行路

Go 处理yaml类型的配置文件

先说一下,这里用到了很多关于反射类型的功能,可能刚开始看代码,如果对反射不熟悉的可能会不是非常清晰,但是同时也是为了更好的理解golang中的反射,同时如果后面...

2000
来自专栏Golang语言社区

go语言中的数组切片:特立独行的可变数组

初看go语言中的slice,觉得是可变数组的一种很不错的实现,直接在语言语法的层面支持,操作方面比起java中的ArrayList方便了许多。但是在使用了一段时...

3504
来自专栏Python爱好者

Python高效编程(一)

2319
来自专栏编程之旅

Objective-C开发编码规范

其实大多数的时间,我们写出来的代码并不仅仅是给自己看的,在协同开发中还有很多人会来Review你的代码,因此,为了不让别人吐槽自己的代码,必须要养成良好的习惯,...

1185
来自专栏Golang语言社区

厚土Go学习笔记 | 30. Stringers的一个练习

让 IPAddr 类型实现 fmt.Stringer 以便用点分格式输出地址。 例如,IPAddr{1, 2, 3, 4} 应当输出 "1.2.3.4"。 这个...

37811
来自专栏守候书阁

实例感受-es6的常用语法和优越性

前几天,用es6的语法重写了我的一个代码库,说是重写,其实改动的并不多,工作量不大。在重写完了的时候,就个人总结了一下es6常用的一些常用的语法和比es5优越的...

853

扫码关注云+社区

领取腾讯云代金券