AGC 008 C - Tetromino Tiling

http://www.elijahqi.win/archives/1599
Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 600 点

問題文
正方形のマスを 4 個繋げた形をテトロミノといいます。 次の 7 種類のテトロミノを順に I, O, T, J, L, S, Z 型と呼ぶことにします。

すぬけ君は I, O, T, J, L, S, Z 型のテトロミノをそれぞれ aI, aO, aT, aJ, aL, aS, aZ 個ずつ持っています。 すぬけ君はこれらのテトロミノのうち K 個を組み合わせ、縦 2 マス、横 2K マスの長方形を作ろうとしています。 このとき、すぬけ君は次のルールに従います。

各テトロミノを置くとき、回転はできるが、反転はできない。
長方形の各マスにはちょうど 1 個のテトロミノが置かれているようにする。
長方形の外部にテトロミノが置かれていないようにする。
すぬけ君はできるだけ大きい長方形を作ろうとしています。 K の最大値を求めてください。

制約
0≤aI,aO,aT,aJ,aL,aS,aZ≤109
aI+aO+aT+aJ+aL+aS+aZ≥1
入力
入力は以下の形式で標準入力から与えられる。

aI aO aT aJ aL aS aZ
出力
K の最大値を出力せよ。 長方形を作ることができない場合、0 を出力せよ。

入力例 1
Copy
2 1 1 0 0 0 0
出力例 1
Copy
3
たとえば、図のように組み合わせればよいです。

入力例 2
Copy
0 0 10 0 0 0 0
出力例 2
Copy
0
長方形を作ることができません。

Score : 600 points

Problem Statement
A tetromino is a figure formed by joining four squares edge to edge. We will refer to the following seven kinds of tetromino as I-, O-, T-, J-, L-, S- and Z-tetrominos, respectively:

Snuke has many tetrominos. The number of I-, O-, T-, J-, L-, S- and Z-tetrominos in his possession are aI, aO, aT, aJ, aL, aS and aZ, respectively. Snuke will join K of his tetrominos to form a rectangle that is two squares tall and 2K squares wide. Here, the following rules must be followed:

When placing each tetromino, rotation is allowed, but reflection is not.
Each square in the rectangle must be covered by exactly one tetromino.
No part of each tetromino may be outside the rectangle.
Snuke wants to form as large a rectangle as possible. Find the maximum possible value of K.

Constraints
0≤aI,aO,aT,aJ,aL,aS,aZ≤109
aI+aO+aT+aJ+aL+aS+aZ≥1
Input
The input is given from Standard Input in the following format:

aI aO aT aJ aL aS aZ
Output
Print the maximum possible value of K. If no rectangle can be formed, print 0.

Sample Input 1
Copy
2 1 1 0 0 0 0
Sample Output 1
Copy
3
One possible way to form the largest rectangle is shown in the following figure:

Sample Input 2
Copy
0 0 10 0 0 0 0
Sample Output 2
Copy
0
No rectangle can be formed.

这题还是被zhx大佬秒了 %%% 太强了 我怎么就没这么厉害的思维呢

题意：给定7种俄罗斯方块的个数 求问 最大 能怎样用K个这样的方块摆出宽度为2*k 高度为2的矩形

求这个k最大 首先通过分析 我们知道 只有1 2 4 5 四个方块 可以使用

所有的二号都能用 我们就扔到最后即可 那么 我们可以看出成双成对的使用1号 4号 5号是没有差别的 意味着 而且 我还可以 从1 4 5中 各选出一个我可以凑出长度为6 高为2的矩形

如果这1 4 5 型号中有0的话 那么我就需要 把非0的型号 都两两成对的取出 然后计算答案即可

那么也就是我们单独考虑1 4 5即可 假如我现在三个数的奇偶性都相同 那么我一定可以都取出做成

矩形 那么再考虑 如果不同的奇偶性 如果奇偶偶 这样的情况 我一定可以只剩下一个拿不出

如果奇奇偶的情况的话 我可以 通过取三个1 造成奇偶偶的情况 这样也是一定只剩下一个拿不出

#include<cstdio>
int a[8];
int main(){
//  freopen("agc.in","r",stdin);
    for (int i=1;i<=7;++i) scanf("%d",&a[i]);
    long long ans=a[2];
    if (!a[1]||!a[4]||!a[5]){
        ans+=a[1]/2*2;ans+=a[4]/2*2;ans+=a[5]/2*2;
    }else{
        ans+=(long long)a[1]+a[4]+a[5];
        if (a[1]%2==a[4]%2&&a[4]%2==a[5]%2);else  ans--;
    }
    printf("%lld",ans);
    return 0;
}

最后

以上就是眯眯眼口红为你收集整理的AGC 008 C - Tetromino Tiling的全部内容，希望文章能够帮你解决AGC 008 C - Tetromino Tiling所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。