#dwango2015prelims5. [dwango2015_prelims_5]電波局
[dwango2015_prelims_5]電波局
问题说明
有一个星球上有一个以正三角形形状排列的城市,该城市中有 个房屋。这个正三角形的特点是:其中一条边平行于东西方向,并且不构成该边的顶点位于最北边的房屋。
每个房屋都用两个整数进行编号。最北边的房屋编号为 (,),第 行从西到东数第 个()房屋的编号为 (,)。
以下是 的例子:
(1,
(2,
(2,
(3,
(3,
(3,
(4,
(4,
(4,
(4,
(5,
(5,
(5,
(5,
(5,
Dwango 公司拥有 个无线电台(编号从 到 ),每个无线电台都向一个正三角形区域(每条边与城市外围的边平行)提供数字内容。
无线电台 有 个整数 、、 ,并且向满足 的所有整数 、 发送信号,将数字内容配送给房屋 (,)。
Dwango 公司计划新建一座电视台,以吸引更多的客户。
有 种设立电视台的方法。请编写一个程序,对于每种设立方法,计算能够获得的新客户数量。
输入
输入是标准输入,格式如下:
: :
- 第 行包含两个整数 和 ,用空格分隔。
- 第 行到第 行提供了已经设立的无线电台的信息。其中第 行提供了无线电台 发出信号的范围,由 个整数 、 和 组成。这表示无线电台 向满足 的所有整数 、 发送信号,将数字内容配送给房屋 (,)。
- 第 行包含一个整数 。
- 第 行到第 行提供了关于新设立方法的信息。其中第 行描述了第 种设立方法中将要设立的无线电台发出信号的范围,由 个整数 、 和 组成。这表示新设立的无线电台将向满足 的所有整数 、 发送信号,计划将数字内容传递给房屋 (,)。
部分得分
本问题设有部分分。
- 当满足 且 且 的数据集 的所有测试用例均正确时,可获得 分。
- 当满足 且 的数据集 的所有测试用例均正确时,除上述分数外,还可额外获得 分。
- 当满足没有额外限制的数据集 的所有测试用例均正确时,除上述分数外,还可额外获得 分。在所有数据集上均正确将获得总共 分。
输出
输出包含 行。第 行()为第 种设立方法中所能覆盖的新房屋数量。
示例1
示例1输出
由已经建立的 个无线电台发送的信号覆盖的房屋范围如下图所示 (○表示被覆盖,×表示未被覆盖)。
×
×
○
×
○
○
×
○
○
○
×
○
○
○
○
○
×
×
○
○
×
○
○
×
○
○
○
×
○
○
○
×
×
×
×
×
第一种设立方法下,新增覆盖的房屋如下图中的+所示,共 个。
×
×
○
×
○
○
○
○
○
○
○
○
○
○
○
○
×
○
○
○
○
○
×
○
○
○
×
×
×
×
×
第二种设立方法下,新增覆盖的房屋如下图中的+所示,共 个。
×
×
○
×
○
○
×
○
○
○
×
○
○
○
○
○
×
×
○
○
×
○
○
×
○
○
○
×
○
○
○
×
×
×