BOJ 31928 : 이상한 트리 해싱

• 문제 링크 boj.kr/31928
• 난이도 : G4
• 태그 : 해 구성하기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321
#define int long long

using namespace std;

using ld = long double;
using pii = pair<int,int>;

template <typename T1, typename T2>
istream& operator>>(istream & ist, pair<T1,T2> &p) {
    ist >> p.first >> p.second;
    return ist;
}
template <typename T>
istream& operator>>(istream & ist, vector<T> &arr) {
    for(auto &u : arr) ist >> u;
    return ist;
}

int log2(int n) {
    int res = 0;
    while(n >>= 1) ++ res;
    return res;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    int t = log2(log2(n));
    if((1ll << (1ll << t)) != n || n <= 4ll) {
        cout << "-1";
        return 0;
    }

    cout << t+1 << " " << t+1 << "\n";
    for(int i = 0; i < t; i++) {
        cout << "1 ";
    }
    cout << "\n";
    for(int i = 0; i < t-1; i++) {
        cout << "1 ";
    }
    cout << 2;
    return 0;
}

---

풀이

유효한 해시값은 $2^{2^k}$이다. 이때 정점의 수는 k+1이다.

k가 2보다 작은 경우 서로 다른 트리를 만들 수 없다. k가 2인 경우 예제 1처럼 할 수 있다. 이 예제 1의 형태를 기본으로 하여 루트에 정점을 붙이면 다른 k에 대해서 답을 구할 수 있다.