← 返回题目列表

Codeforces · 1776/E

E. 穿越铁路

中文机器翻译题面 查看原题

Isona 在火车站。这个车站有两个站台,它们之间有$$$m$$$平行的铁路,可以看作无限的直线。每条铁路都用从 $$$1$$$ 到 $$$m$$$ 的整数进行标识,铁路 $$$1$$$ 距离第一个站台最近,铁路 $$$m$$$ 最远。连续铁路之间以及每个站台与其最近的铁路之间的距离为 $$$1$$$ 米。

Isona 站在第一个站台的内边界上,这时她意识到她忘记验证她的车票了!第二个平台上有一台验证机,就在她当前位置的正对面(因此,Isona 和验证机之间的距离为 $$$m + 1$$$ 米)。只剩下 $$$s$$$ 秒来验证车票,而指定穿越铁路的桥梁距离验证机太远。因此,伊索纳(非常勇敢,但有点粗心)会以与铁路本身垂直的直线穿过铁路。 Isona只能向前跑(不能向后跑),她可以保持静止。当她以最大速度奔跑时,她需要 $$$v$$$ 秒才能穿过 $$$1$$$ 米。她可以以小于或等于她的最大速度的任何速度奔跑。

只有一个问题:$$$n$$$ 火车被编程为通过铁路运输。第 $$$i$$$ 列火车将使用铁路 $$$r_i$$$。它将在 $$$a_i$$$ 秒后开始穿过 Isona 和验证机之间的直线,并在 $$$b_i$$$ 秒后结束。当然,当火车经过时,伊索纳不能穿越铁路。形式上,对于每个 $$$i = 1, \, 2, \, \dots, \, n$$$,Isona 不允许在任何时候 $$$t$$$ 且 $$$a_i < t < b_i$$$ 上铁路 $$$r_i$$$(但她有时可以穿过 $$$a_i$$$ 或 $$$b_i$$$)。

下图总结了情况。图中有 $$$m = 4$$$ 铁路,可见两列火车;穿过铁路 $$$3$$$ 的火车目前正在穿越 Isona 和验证机之间的线路。

Isona 是一位非常出色的跑步者,但每次她必须改变跑步速度时她都会感到疲倦。从现在起 $$$s$$$ 秒内,她必须执行多少次速度更改才能到达其他平台上的验证机器?请注意,一开始 Isona 并未运行。她可以随时开始跑步。她开始跑步的那一刻(即她的速度变为正值)不被视为速度变化。

输入

输入的第一行包含四个整数 $$$n$$$, $$$m$$$, $$$s$$$, $$$v$$$ ($$$1 \leq n \leq 500$$$, $$$1 \leq m \leq 10$$$, $$$1 \leq s, v \leq 10^9$$$) — 的数量火车、铁路数量、Isona 可以穿越铁路的最长时间(以秒为单位),以及她以最大速度穿过 $$$1$$$ 米所需的秒数。

接下来的 $$$n$$$ 行包含三个整数 $$$a_i$$$, $$$b_i$$$, $$$r_i$$$ ($$$1 \leq a_i < b_i \leq 10^9$$$, $$$1 \leq r_i \leq m$$$) — 的开始和结束时间第 $$$i$$$ 列火车穿过 Isona 和验证机之间的直线以及它将使用的铁路。

保证对于经过同一条铁路的任何两列火车 $$$i$$$ 和 $$$j$$$(即 $$$r_i = r_j$$$),它们之间至少有 $$$1$$$ 第二个(即 $$$a_j \ge b_i + 1$$$ 或 $$$a_i \ge b_j + 1$$$)。

输出

打印 Isona 必须执行的最小速度变化次数才能及时到达验证机器。如果这是不可能的,请打印$$$-1$$$。

示例

输入 #1

4 3 5 1
1 2 1
3 4 1
2 3 2
3 4 3

输出 #1

0

输入 #2

3 3 12 2
2 10 1
1 6 2
8 12 3

输出 #2

2

输入 #3

8 4 13 2
1 4 1
5 13 1
1 5 2
6 13 2
1 9 3
10 13 3
1 10 4
11 13 4

输出 #3

2

输入#4

1 1 2 2
1 2 1

输出#4

-1

注意

在第一个样本中,如果 Isona 在时间 $$$t=0$$$ 以最大速度 ($$$1$$$ m/s) 开始运行,她将在火车即将穿过每条铁路时穿过每条铁路,并且她将在不改变速度的情况下于时间 $$$4 = s - 1$$$ 到达另一个站台。

在第二个示例中,速度变化为 $$$2$$$ 的可能解决方案如下:在前 $$$2$$$ 秒内,Isona 以最大速度 ($$$0.5$$$ m/s),然后在 $$$4$$$ 秒内减速至 $$$0.25$$$ m/s,直到到达第二条铁路。此时,她再次以最大速度行驶,直到到达另一个平台。

在第三个示例中,Isona 可以在开始运行之前等待 $$$2$$$ 秒。然后她以最大速度 ($$$0.5$$$ m/s) 跑 $$$5$$$ 秒。之后,她等待 $$$1$$$ 秒不运行(或以 $$$0$$$ m/s 运行),最后她在最后 $$$5$$$ 秒内再次以最大速度运行。总的来说,她改变了两次速度。