logo AlgoBeat OnlineJudge
登录 注册

#214510. [JOISC 2016] 俄罗斯套娃 / Matryoshka

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

你打算开设一家销售俄罗斯套娃的商店。为此,你向工厂订购了 个俄罗斯套娃。这些套娃被编号为 。其中第 个套娃()可以视为一个底面直径为 cm、高为 cm 的中空直圆柱体。每个套娃可以收纳一个底面直径和高度都比它小的其他套娃。被收纳的套娃内部还可以再收纳其他套娃。

某日,你收到工厂发来的通知:你订购的 个套娃不能一次性全部做完,所以第一批只会送达直径大于等于 cm 并且高度小于等于 cm 的所有套娃。你需要预先安排出一个方案,使送来的套娃经过若干次嵌套后,没有被套的套娃数量最小。

的值可能会突然更改。因此,你决定针对 )求出没被套的套娃数量的最小值。询问互相独立。

输入格式

从标准输入中读取以下数据:

  • 行包含两个用空格分隔的整数 。这表示你订购的俄罗斯套娃数量为 个,同时将给出 的值。
  • 接下来的 行中,第 行()包含两个用空格分隔的整数 。这表示第 个俄罗斯套娃的底面直径为 cm,高度为 cm。
  • 接下来的 行中,第 行()包含两个用空格分隔的整数

输出格式

输出共 行。第 行()输出 时,没有被套的套娃数量最小值。

样例

样例输入 1

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

样例输出 1

0
1
2

样例输入 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

样例输出 2

3
1
3
5
0
2
1
3

数据范围与提示

样例 1 解释

  • 时,不存在底面直径不小于 cm 且高度不超过 cm 的俄罗斯套娃,因此输出
  • 时,底面直径不小于 cm 且高度不超过 cm 的俄罗斯套娃为第 号和第 号。第 号套娃可以被收纳进第 号套娃中。此时,未被任何套娃收纳的套娃的最小数量为
  • 时,底面直径不小于 cm 且高度不超过 cm 的俄罗斯套娃为第 号、第 号、第 号和第 号。此时,可以将第 号套娃收纳进第 号套娃中,再将第 号套娃收纳进第 号套娃中。未被任何套娃收纳的套娃的最小数量为

数据范围

所有输入数据满足以下条件:

  • )。
  • )。
  • )。
  • )。

子任务

子任务 1 [11 分]

满足以下条件:

子任务 2 [15 分]

满足以下条件:

子任务 3 [25 分]

满足以下条件:

子任务 4 [49 分]

无额外限制。

翻译由 Qwen3-235B 完成