Problem C
Painting a Fence
You need to hire some people to paint a fence. The fence is composed of $10\, 000$ contiguous sections, numbered from $1$ to $10\, 000$.
You get some offers from painters to help paint the fence. Each painter offers to paint a contiguous subset of fence sections in a particular color. You need to accept a set of the offers, such that:
-
Each section of the fence is painted.
-
At most 3 colors are used to paint the fence.
If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.
Input
The first line of input contains an integer $N$, the number of offers. Then follow $N$ lines, one for each offer, each containing “$C$ $A$ $B$” where $C$ is the color, which is an uppercase string of up to 10 letters, $A$ is the first section and $B$ is the last section to be painted. $1 \leq A \leq B \leq 10\, 000$.
You may assume that $1 \leq N \leq 300$.
Output
Output one line containing the number of offers that need to be accepted, or “IMPOSSIBLE” if there is no acceptable set of offers.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 BLUE 1 5000 RED 5001 10000 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 BLUE 1 6000 RED 2000 8000 WHITE 7000 10000 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 BLUE 1 3000 RED 2000 5000 ORANGE 4000 8000 GREEN 7000 10000 |
IMPOSSIBLE |
| Sample Input 4 | Sample Output 4 |
|---|---|
2 BLUE 1 4000 RED 4002 10000 |
IMPOSSIBLE |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 BLUE 1 6000 RED 4000 10000 ORANGE 3000 8000 |
2 |
