← 返回题目列表

Codeforces · 1776/D

D. 团队合作

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

SWERC 开始后,您经验丰富的 $$$3$$$ 人团队立即意识到比赛的特点是 $$$a$$$ 简单问题、$$$b$$$ 中等问题和 $$$c$$$ 困难问题。解决问题将花费你们中的任何一个 $$$2$$$、$$$3$$$ 或 $$$4$$$ 时间单位,具体取决于问题是简单、中等还是困难。无论问题有多困难,解决问题所花费的最后时间单位都必须花费在使用共享计算机上。

你组织你的努力,以便每个人都以整数时间单位开始(和结束)解决问题。任何给定的问题只能由一名参赛者解决;它需要连续的时间(这取决于问题的难度)。你们中的 $$$3$$$ 都无法一次解决多个问题,但您可以在完成一个问题后立即开始解决新问题。同样,共享计算机一次不能由多个人使用,但任何人都可以在其他人停止使用该计算机后立即开始使用该计算机(以完成当前正在解决的问题)。

鉴于比赛持续 $$$l$$$ 个时间单位,请找出您的团队可以解决的最大问题数。此外,找到一种方法来解决最大数量的问题。

输入

输入只有一行。它包含四个整数 $$$a$$$、$$$b$$$、$$$c$$$、$$$l$$$ ($$$0 \leq a, b, c, \leq 10^4$$$, $$$0 \le l \le 10^5$$$) — 简单、中等和困难问题的数量以及比赛的持续时间。

输出

在第一行,打印一个整数 $$$n$$$ — 您的团队可以解决的最大问题数。

然后,在以下 $$$n$$$ 行的第 $$$j$$$ 行上,打印三个整数 $$$x_j$$$, $$$p_j$$$, $$$q_j$$$ ($$$1 \leq x \leq 3$$$, $$$0 \leq p_j < q_j \leq l$$$) — 解决以下问题的参赛者第 $$$j$$$ 个问题,以及解决第 $$$j$$$ 个问题的开始和结束时间(以比赛开始后经过的时间单位来衡量)。 $$$q_j - p_j$$$ 之间的差异为 $$$2$$$、$$$3$$$ 或 $$$4$$$,具体取决于问题的难度。

最后 $$$n$$$ 行将按结束时间的升序提供:$$$q_1 < q_2 < \cdots < q_n$$$。如果有多种方法可以解决 $$$n$$$ 问题,请输出其中任何一个。

示例

输入 #1

2 1 1 3

输出 #1

2
1 0 2
2 0 3

输入 #2

1 2 3 5

输出 #2

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

输入 #3

0 1 2 2

输出 #3

0

注意

在第一个示例中,第一个参赛者在时间 $$$0$$$ 和时间 $$$2$$$ 之间解决了一个简单问题,而第二个参赛者在时间 $$$0$$$ 和时间 $$$3$$$ 之间解决了一个中等问题。

在第二个示例中,第一位参赛者在时间 $$$0$$$ 和时间 $$$2$$$ 之间解决了一个简单问题,然后还在时间 $$$2$$$ 和时间 $$$5$$$ 之间解决了一个中等问题。与此同时,第二名参赛者在$$$0$$$时间和$$$3$$$时间之间解决了另一个中等问题,而第三名参赛者在$$$0$$$时间和$$$4$$$时间之间解决了一个难题。

在第三个样本中,比赛只有中难问题,没有足够的时间来解决其中任何一个问题。