티스토리 뷰

알고리즘 관련/BOJ

BOJ)11670 초등 수학

JASON 자손9319 2017. 11. 15. 03:39

문제: icpc.me/11670

n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.

이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.

따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, visited[2555], b[7555];
pair<ll, ll> inp[2555];
pair<char, ll> res[2555];
vector<vector<ll>> vt;
vector<ll> ele;
ll getidx(ll x) {
    return lower_bound(ele.begin(), ele.end(), x) - ele.begin() + 1;
}
bool dfs(ll here) {
    if (visited[here])return false;
    visited[here] = true;
    for (auto next : vt[here]) {
        if (!b[next] || dfs(b[next])) {
            b[next] = here;
            return true;
        }
    }
    return false;
}
ll bipartitematching() {
    ll match = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, 0sizeof(visited));
        if (dfs(i))match++;
    }
    return match;
}
int main() {
    scanf("%lld"&n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld"&inp[i].first, &inp[i].second);
        ele.push_back(inp[i].first + inp[i].second);
        ele.push_back(inp[i].first - inp[i].second);
        ele.push_back(inp[i].first*inp[i].second);
    }
    vt.resize(n + 1);
    sort(ele.begin(), ele.end());
    ele.erase(unique(ele.begin(), ele.end()), ele.end());
    for (int i = 1; i <= n; i++) {
        ll x = getidx(inp[i].first + inp[i].second);
        ll y = getidx(inp[i].first - inp[i].second);
        ll z = getidx(inp[i].first*inp[i].second);
        vt[i].push_back(x);
        vt[i].push_back(y);
        vt[i].push_back(z);
    }
    ll match = bipartitematching();
    if (match != n)
        puts("impossible");
    else {
        for (int i = 1; i <= ele.size(); i++) {
            if (!b[i])continue;
            if (inp[b[i]].first + inp[b[i]].second == ele[i - 1])
                res[b[i]] = { '+',ele[i - 1] };
            else if (inp[b[i]].first - inp[b[i]].second == ele[i - 1])
                res[b[i]] = { '-',ele[i - 1] };
            else
                res[b[i]] = { '*',ele[i - 1] };
        }
        for (int i = 1; i <= n; i++
            printf("%lld %c %lld = %lld\n", inp[i].first, res[i].first, inp[i].second, res[i].second);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14938 서강그라운드  (0) 2017.12.04
BOJ)14936 엘리베이터 장난  (0) 2017.12.04
BOJ)11670 초등 수학  (0) 2017.11.15
BOJ)3136 평면도  (0) 2017.11.15
BOJ)14195 DotB  (0) 2017.11.15
BOJ)14748 Flow Graph Complexity  (0) 2017.10.24
댓글
댓글쓰기 폼