시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 2 | 1 | 1 | 100.000% |
You need to hire some people to paint a fence. The fence is composed of 10000 contiguous sections, numbered from 1 to 10000.
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:
If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.
For each test case, there will be:
Limits
5 2 BLUE 1 5000 RED 5001 10000 3 BLUE 1 6000 RED 2000 8000 WHITE 7000 10000 4 BLUE 1 3000 RED 2000 5000 ORANGE 4000 8000 GREEN 7000 10000 2 BLUE 1 4000 RED 4002 10000 3 BLUE 1 6000 RED 4000 10000 ORANGE 3000 8000
Case #1: 2 Case #2: 3 Case #3: IMPOSSIBLE Case #4: IMPOSSIBLE Case #5: 2
In the first test case, accepting both offers will exactly paint the whole fence, 5000 sections each, with no overlap.
In the second case, the painters will overlap, which is acceptable.
In the third case, accepting all four offers would cover the whole fence, but it would use 4 different colours, so this is not acceptable.
In the fourth case, section 4001 cannot be painted.
In the fifth case, we can accept just the first and second offer and successfully paint the fence.
Contest > Google > Code Jam > Google Code Jam 2008 > EMEA Semifinal B1번