B. Candies
n에서부터 줄여나간다.
일단 짝수는 불가능하다. 항상 홀수만 나오기 때문이다.
그렇지 않다면 모든 홀수가 가능하다.
무지성으로 대충 n≡1(mod4)면 2x−1 연산을 사용한 것으로 치고 n≡3(mod4) 라면 2x+1 연산을 사용한 것으로 쳤더니 통과됐다.
void solve() {
int n;
cin >> n;
if (n % 2 == 0) {
cout << "-1\n";
return;
}
vi ans;
while (n != 1) {
if (n % 4 == 3) {
ans.pb(2);
n /= 2;
} else {
ans.pb(1);
n = (n + 1) / 2;
}
}
reverse(all(ans));
cout << sz(ans) << endl;
for (int i: ans) cout << i << ' ';
cout << endl;
}
에디토리얼 풀이
2x+1 이나 2x−1 라는 연산은 이진수로 표현했을 때 가장 오른쪽 비트 20의 왼쪽에 1 을 끼워넣거나 0 을 끼워넣는 연산임을 알 수 있다.
void solve() {
int n;
cin >> n;
if (n % 2 == 0) {
cout << -1 << endl;
} else {
vi ans;
for (int i = 1; i < 30; i++) {
if ((1 << i) > n) break;
if (n & (1 << i)) ans.pb(2);
else ans.pb(1);
}
reverse(all(ans));
cout << sz(ans) << endl;
for (int i: ans) cout << i << ' ';
cout << endl;
}
}
Comments