CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) - B. Candies (800)

B. Candies

$n$에서부터 줄여나간다.

일단 짝수는 불가능하다. 항상 홀수만 나오기 때문이다.

그렇지 않다면 모든 홀수가 가능하다.

무지성으로 대충 $n \equiv 1 \pmod 4$면 $2x-1$ 연산을 사용한 것으로 치고 $n \equiv 3 \pmod 4$ 라면 $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$ 라는 연산은 이진수로 표현했을 때 가장 오른쪽 비트 $2^0$의 왼쪽에 $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;  
   }  
}