# [Bronze I] MEX vs OR [문제 링크](https://www.acmicpc.net/problem/32290) ## 문제 설명 <p>음이 아닌 정수로 구성된 수열 $a$가 주어질 때, 함수 $\text{mex}(a)$는 $a$에 <strong>포함되지 않은</strong> 가장 작은 음이 아닌 정수를 의미합니다.</p> <p>$\text{mex}$에 수열을 대입한 예시에는 다음이 있습니다.</p> <ul> <li>$\text{mex}([1,2,3,4,5])=0$</li> <li>$\text{mex}([0,1,2,3,4])=5$</li> <li>$\text{mex}([0,1,2,4,5])=3$</li> </ul> <p>음이 아닌 두 정수 $x$와 $y$가 주어질 때, $x\,|\,y$를 $x$와 $y$의 비트 OR이라고 부르며, 다음의 규칙에 따라 정의합니다.</p> <ul> <li>2진법에서 $x$와 $y$ 중 <strong>적어도 하나의</strong> $i$번째 자리가 $1$이라면 $x\,|\,y$의 $i$번째 자리가 $1$입니다.</li> <li>2진법에서 $x$와 $y$ <strong>둘 모두</strong> $i$번째 자리가 $0$이라면 $x\,|\,y$의 $i$번째 자리가 $0$입니다.</li> </ul> <p>두 정수의 비트 OR을 구한 예시에는 다음이 있습니다.</p> <ul> <li>$2\,|\,4=010_2\,|\,100_2=110_2=6$</li> <li>$3\,|\,6=011_2\,|\,110_2=111_2=7$</li> <li>$5\,|\,4=101_2\,|\,100_2=101_2=5$</li> </ul> <p>$l \le r$을 만족하는 음이 아닌 세 정수 $l$, $r$, $x$가 주어집니다. 여러분은 다음 수식의 값을 구해야 합니다.</p> <p>$$\text{mex}([(l\,|\,x),((l+1)\,|\,x),\cdots,((r-1)\,|\,x),(r\,|\,x)])$$</p> ## 입력 <p>한 줄에 세 정수 $l$, $r$, $x$가 공백으로 구분되어 주어집니다. ($0 \le l \le r \le 1\,000$, $0 \le x \le 1\,000$)</p> ## 출력 <p>한 줄에 문제의 정답을 출력합니다.</p> ## 풀이 l부터 r까지 전부 x로 xor해준 값 중 등장하지 않은 가장 작은 값을 찾는 문제입니다. l-r 범위가 최대 1001개 이기 때문에 최대 1002개의 수만 확인하면 되기에 브루트포스로 풀립니다. ``` c++ #include<bits/stdc++.h> using namespace std; bool exist[1002]; int main() { ios::sync_with_stdio(0); cin.tie(0); int l, r, x; cin >> l >> r >> x; for(int i=l;i<=r;i++) exist[i|x]=true; for(int i=0;i<=1001;i++) { if(!exist[i]) { cout << i; return 0; } } } ```