[백준 24500] blobblush (C#, C++) - soo:bak

문제 링크

24500번 - blobblush

설명

카드를 골라 XOR 값을 최대화하고, 조건에 맞는 최소 개수의 사전순 집합을 구하는 문제입니다.

접근법

n 이하 카드로 만들 수 있는 최대 XOR은 n을 포함하며, n 이상인 가장 작은 (2의 거듭제곱 - 1) 형태의 수를 찾습니다.

1에서 시작해 2를 곱하고 1을 더하는 과정을 반복하여 n 이상이 되는 목표값을 찾습니다.

만약 목표값이 n과 같다면 n 하나만으로 최대 XOR이 되므로 1장을 출력합니다.

그렇지 않다면 두 장을 선택합니다. 예를 들어 n이 5(101)이고 목표값이 7(111)이면, 5와 2를 선택하면 5 XOR 2 = 7이 됩니다. 여기서 2는 7 XOR 5로 구할 수 있습니다.

이후, 사전순을 위해 두 값을 오름차순으로 출력합니다.

Code

C#

using System;

class Program {
  static void Main() {
    var n = long.Parse(Console.ReadLine()!);

    var lim = 1L;
    while (lim < n)
      lim = lim * 2 + 1;

    if (lim == n) {
      Console.WriteLine(1);
      Console.WriteLine(n);
    } else {
      var other = lim ^ n;
      Console.WriteLine(2);
      Console.WriteLine(Math.Min(other, n));
      Console.WriteLine(Math.Max(other, n));
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n;
  if (!(cin >> n)) return 0;

  ll lim = 1;
  while (lim < n)
    lim = lim * 2 + 1;

  if (lim == n) {
    cout << 1 << "\n" << n << "\n";
  } else {
    ll other = lim ^ n;
    cout << 2 << "\n";
    if (other < n) cout << other << "\n" << n << "\n";
    else cout << n << "\n" << other << "\n";
  }

  return 0;
}