算法
(构造) $O(1)$
对于每种比较关系,若第二个字符是 >
,则它左边的硬币的权值增加 $1$,它右边的硬币的权值减少 $1$;类似地,若第二个字符是 <
,则它右边的硬币的权值增加 $1$,它左边的硬币的权值减少 $1$。
容易发现合理的比较关系下的每种硬币的权值最后只会是 $-2, 0, 2$ 这三种可能之一。
所以,我们可以从小到大遍历这三个值 $i$,并检验这三个硬币中是否存在一个硬币的权值恰等于 $i$,若存在则把该硬币所对应的字符加入答案。
若最后答案不足三个字符,则显然存在构成矛盾的比较关系。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
int main() {
vector<int> c(3);
rep(i, 3) {
string s;
cin >> s;
if (s[1] == '<') c[s[0] - 'A']--, c[s[2] - 'A']++;
else c[s[0] - 'A']++, c[s[2] - 'A']--;
}
string ans;
for (int i = -2; i < 3; i += 2) {
rep(j, 3) {
if (c[j] == i) {
ans += j + 'A';
break;
}
}
}
if (ans.size() < 3) cout << "Impossible\n";
else cout << ans << '\n';
return 0;
}