310050: CF1776D. Teamwork
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Teamwork
题目描述
As soon as SWERC starts, your experienced $ 3 $ -person team immediately realizes that the contest features $ a $ easy problems, $ b $ medium problems, and $ c $ hard problems. Solving a problem will take any of you $ 2 $ , $ 3 $ , or $ 4 $ time units, depending on whether the problem is easy, medium, or hard. Regardless of the difficulty of the problem, the last time unit spent to solve it has to be spent using your shared computer. You organize your efforts so that each of you starts (and ends) solving problems at integer time units. Any given problem can be solved by only one contestant; it requires a contiguous amount of time (which depends on the difficulty of the problem). None of the $ 3 $ of you can solve more than one problem at a time, but you can start solving a new problem immediately after finishing one. Similarly, the shared computer cannot be used by more than one of you at a time, but any of you can start using the computer (to complete the problem currently being solved) immediately after someone else stops using it. Given that the contest lasts $ l $ time units, find the maximum number of problems that your team can solve. Additionally, find one way to solve the maximum number of problems.输入输出格式
输入格式
The input has a single line. It contains four integers $ a $ , $ b $ , $ c $ , $ l $ ( $ 0 \leq a, b, c, \leq 10^4 $ , $ 0 \le l \le 10^5 $ ) — the number of easy, medium, and hard problems, and the duration of the contest.
输出格式
On the first line, print a single integer $ n $ — the maximum number of problems that your team can solve. Then, on the $ j $ -th of the following $ n $ lines, print three integers $ x_j $ , $ p_j $ , $ q_j $ ( $ 1 \leq x \leq 3 $ , $ 0 \leq p_j < q_j \leq l $ ) — the contestant that solves the $ j $ -th problem, and the start and end time for solving the $ j $ -th problem (measured as time units elapsed from the beginning of the contest). The difference $ q_j - p_j $ is $ 2 $ , $ 3 $ , or $ 4 $ , depending on the difficulty of the problem. The last $ n $ lines are to be provided in increasing order of end time: $ q_1 < q_2 < \cdots < q_n $ . If there are multiple ways to solve $ n $ problems, output any of them.
输入输出样例
输入样例 #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说明
In the first sample, the first contestant solves an easy problem between time $ 0 $ and time $ 2 $ while the second contestant solves a medium problem between time $ 0 $ and time $ 3 $ . In the second sample, the first contestant solves an easy problem between time $ 0 $ and time $ 2 $ , and then also solves a medium problem between time $ 2 $ and time $ 5 $ . In the meantime, the second contestant solves another medium problem between time $ 0 $ and time $ 3 $ , while the third contestant solves a hard problem between time $ 0 $ and time $ 4 $ . In the third sample, the contest only has medium and hard problems, and there is not enough time to solve any of them.Input
暂时还没有翻译
Output
**题目描述**
比赛一开始，你们经验丰富的3人团队立即意识到比赛包含a个简单问题，b个中等问题和c个困难问题。解决问题的时间取决于问题的难度，简单、中等和困难问题分别需要2、3或4个时间单位。无论问题难度如何，解决问题的最后一个时间单位必须使用你们共用的电脑。
你们组织自己的努力，让每个人在整数时间单位开始（和结束）解决问题。任何给定的问题只能由一个参赛者解决；它需要一段连续的时间（这取决于问题的难度）。你们3个中的任何一个都不能同时解决一个问题，但可以在完成一个问题后立即开始解决新问题。同样，共用的电脑一次只能由一个人使用，但你们中的任何一个人都可以在别人停止使用后立即开始使用电脑（完成当前正在解决的问题）。
鉴于比赛持续l个时间单位，找出你们团队可以解决的最大问题数量。此外，找出解决最多问题的一种方式。
**输入输出格式**
**输入格式**
输入共有一行，包含4个整数a, b, c, l (0 ≤ a, b, c ≤ 10^4, 0 ≤ l ≤ 10^5) — 简单、中等和困难问题的数量以及比赛的持续时间。
**输出格式**
首先，在一行中打印一个整数n — 你们团队可以解决的最大问题数量。
然后，在接下来的n行中的第j行，打印三个整数x_j, p_j, q_j (1 ≤ x ≤ 3, 0 ≤ p_j < q_j ≤ l) — 解决第j个问题的参赛者，以及解决第j个问题的开始和结束时间（以从比赛开始经过的时间单位衡量）。差值q_j - p_j是2、3或4，取决于问题的难度。
最后的n行应按结束时间的递增顺序提供：q_1 < q_2 < ... < 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之间解决了一个困难问题。
在第三个样例中，比赛只有中等和困难问题，而且没有足够的时间解决任何一个问题。**题目描述** 比赛一开始，你们经验丰富的3人团队立即意识到比赛包含a个简单问题，b个中等问题和c个困难问题。解决问题的时间取决于问题的难度，简单、中等和困难问题分别需要2、3或4个时间单位。无论问题难度如何，解决问题的最后一个时间单位必须使用你们共用的电脑。 你们组织自己的努力，让每个人在整数时间单位开始（和结束）解决问题。任何给定的问题只能由一个参赛者解决；它需要一段连续的时间（这取决于问题的难度）。你们3个中的任何一个都不能同时解决一个问题，但可以在完成一个问题后立即开始解决新问题。同样，共用的电脑一次只能由一个人使用，但你们中的任何一个人都可以在别人停止使用后立即开始使用电脑（完成当前正在解决的问题）。 鉴于比赛持续l个时间单位，找出你们团队可以解决的最大问题数量。此外，找出解决最多问题的一种方式。 **输入输出格式** **输入格式** 输入共有一行，包含4个整数a, b, c, l (0 ≤ a, b, c ≤ 10^4, 0 ≤ l ≤ 10^5) — 简单、中等和困难问题的数量以及比赛的持续时间。 **输出格式** 首先，在一行中打印一个整数n — 你们团队可以解决的最大问题数量。 然后，在接下来的n行中的第j行，打印三个整数x_j, p_j, q_j (1 ≤ x ≤ 3, 0 ≤ p_j < q_j ≤ l) — 解决第j个问题的参赛者，以及解决第j个问题的开始和结束时间（以从比赛开始经过的时间单位衡量）。差值q_j - p_j是2、3或4，取决于问题的难度。 最后的n行应按结束时间的递增顺序提供：q_1 < q_2 < ... < 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之间解决了一个困难问题。 在第三个样例中，比赛只有中等和困难问题，而且没有足够的时间解决任何一个问题。
比赛一开始，你们经验丰富的3人团队立即意识到比赛包含a个简单问题，b个中等问题和c个困难问题。解决问题的时间取决于问题的难度，简单、中等和困难问题分别需要2、3或4个时间单位。无论问题难度如何，解决问题的最后一个时间单位必须使用你们共用的电脑。
你们组织自己的努力，让每个人在整数时间单位开始（和结束）解决问题。任何给定的问题只能由一个参赛者解决；它需要一段连续的时间（这取决于问题的难度）。你们3个中的任何一个都不能同时解决一个问题，但可以在完成一个问题后立即开始解决新问题。同样，共用的电脑一次只能由一个人使用，但你们中的任何一个人都可以在别人停止使用后立即开始使用电脑（完成当前正在解决的问题）。
鉴于比赛持续l个时间单位，找出你们团队可以解决的最大问题数量。此外，找出解决最多问题的一种方式。
**输入输出格式**
**输入格式**
输入共有一行，包含4个整数a, b, c, l (0 ≤ a, b, c ≤ 10^4, 0 ≤ l ≤ 10^5) — 简单、中等和困难问题的数量以及比赛的持续时间。
**输出格式**
首先，在一行中打印一个整数n — 你们团队可以解决的最大问题数量。
然后，在接下来的n行中的第j行，打印三个整数x_j, p_j, q_j (1 ≤ x ≤ 3, 0 ≤ p_j < q_j ≤ l) — 解决第j个问题的参赛者，以及解决第j个问题的开始和结束时间（以从比赛开始经过的时间单位衡量）。差值q_j - p_j是2、3或4，取决于问题的难度。
最后的n行应按结束时间的递增顺序提供：q_1 < q_2 < ... < 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之间解决了一个困难问题。
在第三个样例中，比赛只有中等和困难问题，而且没有足够的时间解决任何一个问题。**题目描述** 比赛一开始，你们经验丰富的3人团队立即意识到比赛包含a个简单问题，b个中等问题和c个困难问题。解决问题的时间取决于问题的难度，简单、中等和困难问题分别需要2、3或4个时间单位。无论问题难度如何，解决问题的最后一个时间单位必须使用你们共用的电脑。 你们组织自己的努力，让每个人在整数时间单位开始（和结束）解决问题。任何给定的问题只能由一个参赛者解决；它需要一段连续的时间（这取决于问题的难度）。你们3个中的任何一个都不能同时解决一个问题，但可以在完成一个问题后立即开始解决新问题。同样，共用的电脑一次只能由一个人使用，但你们中的任何一个人都可以在别人停止使用后立即开始使用电脑（完成当前正在解决的问题）。 鉴于比赛持续l个时间单位，找出你们团队可以解决的最大问题数量。此外，找出解决最多问题的一种方式。 **输入输出格式** **输入格式** 输入共有一行，包含4个整数a, b, c, l (0 ≤ a, b, c ≤ 10^4, 0 ≤ l ≤ 10^5) — 简单、中等和困难问题的数量以及比赛的持续时间。 **输出格式** 首先，在一行中打印一个整数n — 你们团队可以解决的最大问题数量。 然后，在接下来的n行中的第j行，打印三个整数x_j, p_j, q_j (1 ≤ x ≤ 3, 0 ≤ p_j < q_j ≤ l) — 解决第j个问题的参赛者，以及解决第j个问题的开始和结束时间（以从比赛开始经过的时间单位衡量）。差值q_j - p_j是2、3或4，取决于问题的难度。 最后的n行应按结束时间的递增顺序提供：q_1 < q_2 < ... < 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之间解决了一个困难问题。 在第三个样例中，比赛只有中等和困难问题，而且没有足够的时间解决任何一个问题。