CF1776D Teamwork

SWERC 比赛一开始，你们经验丰富的三人队伍立刻发现本次比赛包含 $a$ 道简单题，$b$ 道中等题，以及 $c$ 道难题。解答一道题分别需要 $2$、$3$ 或 $4$ 个时间单位，具体取决于题目的难度。无论题目难度如何，解题的最后一个时间单位必须使用你们共用的计算机。 你们组织分工，使得每个人都在整数时间点开始（并结束）解题。每道题只能由一名队员独立完成，且需要连续的时间（由题目难度决定）。三人中每个人在同一时刻只能解一道题，但完成一道题后可以立刻开始下一道题。同样，共用计算机在同一时刻只能被一人使用，但任何人都可以在别人用完后立即使用计算机完成当前题目。 已知比赛总时长为 $l$ 个时间单位，求你们队伍最多能解出多少道题。同时，给出一种达到最大解题数的安排方案。

输入仅一行，包含四个整数 $a$、$b$、$c$、$l$（$0 \leq a, b, c \leq 10^4$，$0 \le l \le 10^5$），分别表示简单题、中等题、难题的数量，以及比赛时长。

第一行输出一个整数 $n$，表示你们队伍最多能解出的题目数。 接下来 $n$ 行，每行输出三个整数 $x_j$、$p_j$、$q_j$（$1 \leq x_j \leq 3$，$0 \leq p_j < q_j \leq l$），分别表示第 $j$ 道题由第 $x_j$ 位队员解答，解题的开始时间和结束时间（从比赛开始算起）。$q_j - p_j$ 分别为 $2$、$3$ 或 $4$，取决于题目的难度。 输出的 $n$ 行必须按结束时间严格递增排序：$q_1 < q_2 < \cdots < q_n$。如果有多种方案，输出任意一种均可。

在第一个样例中，第一位队员在 $0$ 到 $2$ 时间段解了一道简单题，第二位队员在 $0$ 到 $3$ 时间段解了一道中等题。 在第二个样例中，第一位队员先在 $0$ 到 $2$ 时间段解了一道简单题，然后又在 $2$ 到 $5$ 时间段解了一道中等题。同时，第二位队员在 $0$ 到 $3$ 时间段解了一道中等题，第三位队员在 $0$ 到 $4$ 时间段解了一道难题。 在第三个样例中，比赛只包含中等题和难题，但时间不足以解出任何一道题。 由 ChatGPT 4.1 翻译