순서가 뒤섞인 수열이 주어졌을 때 원래의 수열의 순서를 구하는 문제입니다.
수열에서 다음 수로 가는 방법은 두 가지가 있습니다.
3으로 나누어떨어질 때, 3으로 나눈다.
2를 곱한다.
뒤섞인 수열을 다시 원래 수열로 돌리는 방법은 수열에서 2가지 방법을 해서 나오는 수와 연결을 해주면 됩니다.
예를 들어 3의 다음 숫자를 찾을 때 3으로 나눈 1이 수열에 포함되어 있는지 보고
2를 곱한 6이 수열에 포함되어 있는지 봐서 연결을 해주시면 됩니다.
다 연결해 준 뒤보면 들어오는 간선이 없는 번호가 하나 있을 겁니다.
그것이 시작번호이고 그대로 그래프 탐색을 해주시면 수열을 차례대로 구할 수 있습니다.
문제는 스폐셜 저지라고 되어있지만
답은 하나밖에 없습니다.
그 이유는 답이 여러 가지가 되려면 어떠한 수에서 두 가지 방법으로 다음 수를 구해야 가능합니다.
그런데 한 번에 한 가지 방법으로 밖에 다음 수를 구할 수 있기 때문에
똑같은 수가 수열에 포함되어 있어야지 여러 가지 방법이 가능합니다.
하지만 같은 수가 수열에 두 번 나올 수 없습니다.
\(x = 2^a \times 3^{-b} \times x\) 가 성립을 해야 수열에 두 번 같은 수가 나올 수 있는데
2,3 둘 다 소수라서 성립을 할 수 없습니다.
그래서 경로는 하나밖에 없습니다!
이예ㅔ에ㅔ에에에
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define vll vector <ll>
#define all(x) (x).begin(), (x).end()
#define eb emplace_back
using namespace std;
int main() {
FIO;
int n, root;
cin >> n;
vll v(n), in(n), f(n, -1);
FOR(i, 0, n - 1) cin >> v[i];
sort(all(v));
FOR(i, 0, n - 1) {
ll x = v[i];
int idx = lower_bound(all(v), x * 2) - v.begin();
if (idx < n && x * 2 == v[idx]) f[i] = idx, in[idx]++;
if (x % 3) continue;
idx = lower_bound(all(v), x / 3) - v.begin();
if (idx < n && x / 3 == v[idx]) f[i] = idx, in[idx]++;
}
FOR(i, 0, n - 1) if (!in[i]) root = i;
for (; root != -1; root = f[root])
cout << v[root] << ' ';
return 0;
}