비트연산자는 같은 자리끼리만 연산을 하고, 서로 다른 자리에는 영향을 주지 않습니다. 그러므로 0과 1만 다루는 버전의 문제를 해결한 다음 그 문제 10개를 합치면 0부터 1023까지 다룰 수 있습니다.

@jh05013 음...

제가 0또는 1로 주어져도 이해를 잘 못할것같습니다 .ㅠ.ㅠ

단순히 입력이

1000

| 1
^ 0
& 0
| 1
^ 1
| 0
& 1
| 0
^ 1
& 0
.... 

이렇게 임의로 5*10^5 만큼 들어와도 연산자가

^
&
|

식으로나
&
^

식으로 정렬될수 있다는 것 자체는 이해가 되는데 프로세스가 이해가 되질 않습니다... ㅠ.ㅠ. 분명히 and, or, not(또는 xor) 으로 표현할 수 없는 명제는 존재하지 않으니(functionally complete이므로) 반드시 표현할 수 있다고 믿기는하는데요. 근데 그 과정이 이해가 안됩니다....

분명히   ((((((임의의수(0또는 1)|1)^0)&0)|1)^1)|0)&1)|0 .... 이런식으로 작성될건데 분배법칙을 이용한것이아닌

단순히 주어진 연산을 순서대로 연산해나간뒤 -> (제가 이해하지못하는 프로세스) 를 거쳐서 -> (((임의의수^a)&b)|c) 로 출력된다는게 그 프로세스가 잘 이해가 안됩니다 도움부탁드립니다 ㅠ.ㅠ

그러니까 어떠한 입력에도 반드시 

|
&
^

또는

&
^

로 완성시키더라구요. 그걸 잘 이해를 못하겠습니다 .ㅠ.ㅠ

모든 연산에 0과 1만 들어 있고, 0부터 1023까지가 아니라 0부터 1까지만 CALPAS에 들어온다고 가정하면 다음의 네 가지 경우만 존재합니다.

1) 0을 넣었을 때 0, 1을 넣었을 때 0

2) 0을 넣었을 때 0, 1을 넣었을 때 1

3) 0을 넣었을 때 1, 1을 넣었을 때 0

4) 0을 넣었을 때 1, 1을 넣었을 때 1

각각의 경우를 0 또는 1인 어떤 i, j, k에 대해 ^i &j |k로 나타낼 수 있습니다. (물론 모든 경우가 같은 i, j, k를 사용하진 않습니다.) 프로그램이 아무리 복잡해도 저 네 경우 중 하나일 테니 어느 경우에 해당하는지 보고, 그에 해당하는 ^i &j |k를 출력하면 됩니다.

비트 단위로 나눠서 생각해보시면, 각 비트별로 최종적으로 나올 수 있는 결과는 다음의 4가지가 있습니다.

1. 무조건 1이 되는 경우

2. 무조건 0이 되는 경우

3. 처음 입력된 비트와 같은 비트인 경우

4. 처음 입력된 비트와 반대 비트인 경우

딱 한자리 수만 놓고 봤을 때 각각 4가지 경우가 어떤 과정을 거쳐서 도출이 되는지 보면,

어떤 수와 & 0을 하는 경우 결과는 반드시 0이 됩니다. & 1을 하는 경우 기존 비트 값이 유지됩니다.

| 0을 하는 경우 기존 비트 값이 유지됩니다. | 1을 하는 경우 결과는 반드시 1이 됩니다.

^ 0을 하는 경우 기존 비트 값이 유지됩니다. ^ 1을 하는 경우 결과는 기존 비트와 반대 값이 됩니다.

이제 이 과정을 전체 연산 순서를 거쳐보면 결과적으로 각 비트별로 저 4가지 중에 어떤 값이 되는 지가 정해져야 하는데요, 그러면 이제 그 최종 결과값을 보고 어떤 연산을 해야 그 결과를 만들 수 있는 지를 도출해낼 수가 있습니다.

1. 무조건 1이 되는 경우 : | 1에 해당하는 경우입니다. 해당 비트 위치값이 1인 숫자와 or 연산 해주면(나머지는 0) 그 위치만 무조건 1로 만들고 나머지 위치 비트는 입력 결과가 유지됩니다.

2. 무조건 0이 되는 경우 : & 0에 해당하는 경우입니다. 해당 비트 위치 값이 0인 숫자와 and 연산해주면(나머지는 1) 그 위치만 무조건 0으로 만들고 나머지 위치 비트는 입력 결과가 유지됩니다.

3. 기존 비트 입력이 유지되는 경우 : 이 경우는 딱히 신경 안써도 되겠죠. 

4. 기존 비트 입력과 반대가 되는 경우 : ^ 1에 해당하는 경우입니다. 해당 비트 위치 값이 1인 숫자와 xor 연산해주면(나머지는 0) 그 위치 비트는 입력 값과 반대로 만들고 나머지는 입력 결과가 유지됩니다.

그러면 최종 4가지 케이스를 구하면 각각 최종적으로 어떤 값과 and, or, xor 연산을 하게 만들어주면 처음 연산 시퀀스와 동일한 결과가 나오는지 구할 수 있습니다. 그걸 순서대로 출력해주면 됩니다. 아래는 제가 위 설명과 완전 동일한 방식으로 제출해서 푼 코드입니다. 설명이랑 같이 코드 읽어보시면 조금 이해되지 않을까요..

코드에서 state[i] 위치값 0,1,2,3이 각각 위에 적은 케이스 1,2,3,4에 해당하는 지 여부입니다.

http://codeforces.com/contest/...

@jh05013 님 설명감사합니다. ㅠ.ㅠ 제가 오늘 일어나면서도 잠결에 0과 1023사이의 수가 아닌 0과 1만을 둔 경우에는 어떤식으로 결과값을 유추해야할까 생각은 했는데 더 깊이는 생각을 못했어요..... 그게 제 노력 수준과 실력 수준이겠죠...

@jwvg0425 님 코드 감사드립니다. 설명이 이해가 잘되네요. ㅠ.ㅠ 헉헉 ... 천천히 코드 보면서 또 써주신 설명 읽어나가면서 문제 조건을 이해해나가는게 우선일거같아요.

그 뒤에서야 다른 사람들 답을 보면서 또 다르게 어떻게 풀었나 경우를 생각해볼 수 있겠어요. 감사드립니다. 정말 ..ㅠㅠ

이 문제가 제 벽인거 같은데 이 벽을 넘어보겠습니다. 쉬운문제인거같습니다.!! 라는 ...생각이 들듯말듯합니다.

두 분 모두 주말 잘보내세요 ^^..