`
kmplayer
  • 浏览: 509947 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

国际大学生程序设计竞赛例题_2.2L形覆盖

 
阅读更多
1,题意:给定一个m*n长的矩形,问用2*3的L形能否完全覆盖.
2,解决:充要条件(m*n)%8==0
证明:
充分性:
只有两种情况:
(1)m==4,n==2,显然可以
(2)m或n%8==0,例m%8==0,n显然是2和3的和组合,这样可以划分成多个8*2和8*3的组合.
如下图:
必要性:(棋盘染色法)
(1)染成黑白相间的,黑==白,因此(m*n)%2==0
(2)染成一排白,一排黑,L形状不是1黑3白就是3黑1白,因此黑和白均为4的倍数,总数为8的倍数.
得证.
3,实例代码:
#include <iostream>
using namespace std;

int main()
{
    freopen("2.2.in","r",stdin);
    int m,n;
    while(cin>>m>>n,m)
    {
        if( m>1&&n>1&&(m*n)%8==0 )
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}
  • 2.2.rar (892 Bytes)
  • 下载次数: 0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics