[Easy] TheLotteryBothDivs
Topcoder SRM 502 Div1
s[i] 가 s[j] 를 suffix로 가진다면 s[i] 를 suffix로 가지는 당첨번호는 당연히 s[j] 를 suffix로 가지게 된다.
따라서 s[i]는 답을 구하는데 전혀 쓸모가 없어진다.
이런 string들을 모두 삭제했다고 하자.
그렇다면 남은 string들을 suffix로 가지는 당첨번호들은 중복없이 모두 독립적이다.
따라서 답은 sum( 10^(-len(s[i])) )
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 <cmath> | |
| #include <vector> | |
| #include <string> | |
| #include <algorithm> | |
| using namespace std; | |
| class TheLotteryBothDivs { | |
| public: | |
| double find(vector<string> goodSuffixes) { | |
| for (auto& s : goodSuffixes) { | |
| reverse(s.begin(), s.end()); | |
| } | |
| sort(goodSuffixes.begin(), goodSuffixes.end()); | |
| for (int i = 1; i < goodSuffixes.size(); ++i) { | |
| if (goodSuffixes[i].compare(0, goodSuffixes[i - 1].length(), goodSuffixes[i - 1]) == 0) { | |
| goodSuffixes.erase(goodSuffixes.begin() + i); | |
| --i; | |
| } | |
| } | |
| double ans = 0; | |
| for (auto& s : goodSuffixes) { | |
| ans += pow(10, 9 - s.length()); | |
| } | |
| return ans / 1000000000.0; | |
| } | |
| }; |