| 题目名称 | 1521. [POJ1038]Bugs Integrated, Inc. |
|---|---|
| 输入输出 | exameight.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 29 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-02-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：5， 通过率：80% | ||||
 dydxh |
100 | 3.642 s | 0.79 MiB | C++ |
 AAAAAAAAAA |
100 | 4.224 s | 1.24 MiB | C++ |
 Shirry |
100 | 4.934 s | 1.13 MiB | C++ |
 cstdio |
100 | 5.774 s | 6.67 MiB | C++ |
|
dydxh |
0 | 0.000 s | 0.00 MiB | C++ |
| 本题关联比赛 | |||
| exam | |||
| 关于 Bugs Integrated, Inc. 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
1521. [POJ1038]Bugs Integrated, Inc.
★★★ 输入文件：exameight.in
输出文件：exameight.out
简单对比时间限制：1 s 内存限制：29 MiB
【英文原题】
Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.
Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task
You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.
【题目描述】
Bugs Integrated,Inc. 是高级存储芯片的主要制造商。他们正在开始生产新的 $6$ TB Q-RAM 芯片。每个芯片由以 $2×3$ 的矩形排列的六个方形硅片块组成。Q-RAM 芯片的制造方式是将一块长方形的大硅片分成 $N×M$ 个方形硅片块。然后仔细测试所有方形硅片块，坏的用黑色标记。
最后，将硅片切割成存储芯片。每个芯片由 $2×3$（或$3×2$）单位的方形硅片块组成。当然，任何芯片都不能包含坏的（标记的）方形硅片块。由于技术限制，不可能每一个好的方形硅片块都能成为某些存储芯片的一部分。公司希望尽可能少地浪费好的方形硅片块。因此他们想知道如何切割硅片才能得到尽可能多的芯片。
现您将获得几个硅片的尺寸和其每个硅片所有坏方形硅片块的列表。你的任务是编写一个程序，计算每个硅片最多可以切出芯片的数量。
【输入格式】
输入包含多组数据。
输入文件第一行是数据组数 $T$。
接下来是 $T$ 组数据。
每组数据的第一行有三个正数 $n,m,k$，其中 $k$ 是硅片中坏方块的个数。
接下来有 $k$ 行，每行两个整数 $(x,y)$，表示 坏方块的坐标（左上角坐标为 $(1,1)$,右下角坐标为 $(N,M)$）。
【输出格式】
【样例输入】
2 6 6 5 1 4 4 6 2 2 3 6 6 4 6 5 4 3 3 6 1 6 2 6 4
【样例输出】
3 4