[Easy] YetAnotherIncredibleMachine
Topcoder SRM 513 Div1
어떤 mount[i] 가 ball[k] < mount[i] < ball[k+1] 인 위치에 있다고 해보자
이 mount에 걸린 막대는 항상 [ball[k]+1, ball[k+1]-1] 사이의 구간에 존재해야 한다.
이 구간을 벗어나면 항상 ball과 부딪치기 때문이다.
따라서 각 mount마다 막대가 존재할 수 있는 위치의 가짓수를 쉽게 구할 수 있고
이걸 다 곱하면 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <vector> | |
| #include <algorithm> | |
| using namespace std; | |
| class YetAnotherIncredibleMachine { | |
| public: | |
| int countWays(vector<int> platformMount, vector<int> platformLength, vector<int> balls) { | |
| balls.push_back(-100000); | |
| balls.push_back(100000); | |
| sort(balls.begin(), balls.end()); | |
| int ret = 1; | |
| for (int i = 0; i + 1 < balls.size(); ++i) { | |
| int st = balls[i], ed = balls[i + 1]; | |
| for (int j = 0; j < platformMount.size(); ++j) { | |
| if (platformMount[j] < st || platformMount[j] > ed) { | |
| continue; | |
| } | |
| int mst = max(st + 1, platformMount[j] - platformLength[j]); | |
| int med = min(ed - 1, platformMount[j] + platformLength[j]); | |
| int val = max(0, med - mst - platformLength[j] + 1); | |
| ret = (long long)ret * val % 1000000009; | |
| } | |
| } | |
| return ret; | |
| } | |
| }; |