📝 문제 정보#
🧐 관찰 및 접근#
- $(0, 0) \rightarrow (X, Y)$ 로 이동해야한다.
- 과정을 최소화할 필요는 없는데, 4000번 안쪽으로 가야한다.
- 일단 음.. 다음과 같은 연산들을 추가로 정의할 수 있겠다.
- $a$개의 $R$을 사용해서 $x$ 좌표를 $2^a - 1$ 만큼 증가시킨다.
- $b$개의 $U$을 사용해서 $y$ 좌표를 $2^b - 1$ 만큼 증가시킨다.
- 한 연산을 반복해서 사용할 수는 없다.
- 위 연산을 아래에서는 각각 $A, B$ 연산이라고 하겠다.
- 예제 1번인 $(8, 3)$은 $(7+1, 3)$로 변환하면 된다는걸 알 수 있다.
- 관찰을 조금 더 해야할 것 같다.
- $A, B$ 연산의 횟수는 최대 1회 차이날 수 있다.
- 번갈아가며 사용해야하므로
- $A ,B$ 연산의 결과는 언제나 홀수이다.
- 연산은 $a, b = 1$이 아닌 이상 3개로 쪼갤 수 있다.
- 연산에 2개를 더하는건 쉽게 할 수 있다는 뜻
- 이건 직관인데, 그리디하게 가장 큰 연산을 가져가는게 될 수도 있지 않을까 싶다.
- 21 = 15 + 3 + 3 = 7 + 7 + 7
- 43 = 31 + 7 + 3 + 1 + 1 = 15 + 15 + 7 + 3 + 3
- 음.. 되는거같은데 흠 이걸 어떻게 증명할 수 있지?
- 뭔가 위에서 3개로 쪼개진다고 했듯이 31 = 15 + 15 + 1인데, 31을 안쓰면 15를 두번쓰는건 사실상 확정이고, 이때 뒤에있는 1을 훔쳐와서 두개를 줄이고 / 뒤에 1을 훔쳐오게되면서 2개가 늘어나면 또이또이고, 만약에 뒤에 1이 남아있었다면 하나 줄고 같은 느낌으로 그리디가 증명 될 것 같다.
- $A, B$ 연산의 횟수는 최대 1회 차이날 수 있다.
- 믿고 짜볼까? 귀찮으니 PQ로 관리하자.
- ㅋㅋㅋㅋ X, Y에 대해 같은 로직인데 함수화하기 귀찮아서 그대로 박았더니 코드가 더럽다…
💻 풀이#
- 코드 (C++):
void solve(){
vector<ll> int_to_op;
int_to_op.push_back(0);
while(int_to_op.back() < 1e18) int_to_op.push_back(int_to_op.back()*2 + 1);
map<ll, int> op_to_int;
rep(i, 0, int_to_op.size()) op_to_int[int_to_op[i]] = i;
ll X, Y; cin >> X >> Y;
priority_queue<ll> Xpq, Ypq;
while(X){
int ok = 0, ng = int_to_op.size();
while(ng - ok > 1){
int mid = (ok + ng) >> 1;
if(int_to_op[mid] <= X) ok = mid;
else ng = mid;
}
Xpq.push(ok);
X -= int_to_op[ok];
}
while(Y){
int ok = 0, ng = int_to_op.size();
while(ng - ok > 1){
int mid = (ok + ng) >> 1;
if(int_to_op[mid] <= Y) ok = mid;
else ng = mid;
}
Ypq.push(ok);
Y -= int_to_op[ok];
}
while(abs((int)Xpq.size() - (int)Ypq.size()) > 1){
if(Xpq.size() < Ypq.size()){
if(Xpq.size() == 0 || Xpq.top() == 1){
cout << "impossible";
return;
}
ll top = Xpq.top(); Xpq.pop();
Xpq.push(top-1);
Xpq.push(top-1);
Xpq.push(1);
}
else{
if(Ypq.size() == 0 || Ypq.top() == 1){
cout << "impossible";
return;
}
ll top = Ypq.top(); Ypq.pop();
Ypq.push(top-1);
Ypq.push(top-1);
Ypq.push(1);
}
}
string ans = "";
if(Xpq.size() >= Ypq.size()){
while(!Xpq.empty() || !Ypq.empty()){
rep(i, 0, Xpq.top()) ans += 'R';
Xpq.pop();
if(Ypq.empty()) break;
rep(i, 0, Ypq.top()) ans += 'U';
Ypq.pop();
}
}
else{
while(!Xpq.empty() || !Ypq.empty()){
rep(i, 0, Ypq.top()) ans += 'U';
Ypq.pop();
if(Xpq.empty()) break;
rep(i, 0, Xpq.top()) ans += 'R';
Xpq.pop();
}
}
if(ans.size() <= 4000) cout << ans;
else cout << "impossible";
}