시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 4 4 21.053%

문제

레지스터는 계산을 하기 위해서 N비트를 저장한다. 시프트 레지스터는 레지스터의 특수한 형태로, 모든 비트를 한 자리씩 시프트 시킬 수 있다.

시프트 레지스터의 결과를 이용해 다음과 같이 바이너리 유사난수를 얻을 수 있다. 크기가 N인 시프트 레지스터에 a1, a2, ..., aN이 저장되어 있다. 클럭틱마다 레지스터는 가장 오른쪽 비트 aN을 출력한다. 다른 비트는 모두 오른쪽으로 한 칸 이동하게 된다. 첫 번째 비트 a′1은 다음과 같은 방법으로 구할 수 있다.

레지스터의 모든 비트는 아래 그림과 같이 스위치를 통해 XOR 게이트와 연결되어 있다. 각각의 비트 i마다 스위치 si(1 또는 0)가 존재하며, 스위치는 ai를 XOR 게이트로 보낼지 말지를 결정하게 된다. ki = si·ai라고 했을 때, a′1은 XOR게이트의 출력값 XOR(k1, ..., kN)이 된다. (k1, ..., kN에서 1의 개수가 홀수개이면 XOR(k1, ..., kN) = 1이고, 아니면 0이다)

  • a′1 = XOR(k1, ..., kN)
  • a′i = ai-1 for 2 ≤ i ≤ N
  • output = aN

위의 예제에서 틱 1에서 a1은 다음과 같이 XOR(1·1, 0·0, 1·1, 1·1, 0·0, 1·0, 1·1) = 0

시프트 레지스터의 결과 중 처음 2N개가 주어진다. 이때, 스위치 값 si를 결정하는 프로그램을 작성하시오.

입력

첫째 줄에 시프트 레지스터의 크기 N이 주어진다. (1 ≤ N ≤ 750) 둘째 줄에는 시프트 레지스터의 결과중 처음 2N개가 주어지며, 0 또는 1이다.

출력

입력으로 주어진 레지스터 출력 결과를 갖는 스위치 세팅이 존재하는 경우에는 si를 공백으로 구분해서 출력하고, 존재하지 않는 경우에는 -1을 출력한다.

가능한 스위치 세팅이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

7
1 0 0 1 1 0 1 0 1 1 0 0 1 1

예제 출력 1

1 0 1 1 0 1 1
W3sicHJvYmxlbV9pZCI6IjcwNTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWQ1MDRcdWQyYjggXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWIyOTQgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgTlx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YzJkY1x1ZDUwNFx1ZDJiOCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWIyOTQgXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwXHVjNzU4IFx1ZDJiOVx1YzIxOFx1ZDU1YyBcdWQ2MTVcdWQwZGNcdWI4NWMsIFx1YmFhOFx1YjRlMCBcdWJlNDRcdWQyYjhcdWI5N2MgXHVkNTVjIFx1Yzc5MFx1YjlhY1x1YzUyOSBcdWMyZGNcdWQ1MDRcdWQyYjggXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1ZDUwNFx1ZDJiOCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWM3MjBcdWMwYWNcdWIwOWNcdWMyMThcdWI5N2MgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDA2Y1x1YWUzMFx1YWMwMCBOXHVjNzc4IFx1YzJkY1x1ZDUwNFx1ZDJiOCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM1ZDAgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPk48XC9zdWI+XHVjNzc0IFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1ZDA3NFx1YjdlZFx1ZDJmMVx1YjljOFx1YjJlNCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJlNDRcdWQyYjggYTxzdWI+TjxcL3N1Yj5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5NzggXHViZTQ0XHVkMmI4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmU0NFx1ZDJiOCBhJnByaW1lOzxzdWI+MTxcL3N1Yj5cdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZTQ0XHVkMmI4XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWQxYjVcdWQ1NzQgWE9SIFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViZTQ0XHVkMmI4IGlcdWI5YzhcdWIyZTQgXHVjMmE0XHVjNzA0XHVjZTU4IHM8c3ViPmk8XC9zdWI+KDEgXHViNjEwXHViMjk0IDApXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCwgXHVjMmE0XHVjNzA0XHVjZTU4XHViMjk0IGE8c3ViPmk8XC9zdWI+XHViOTdjIFhPUiBcdWFjOGNcdWM3NzRcdWQyYjhcdWI4NWMgXHViY2Y0XHViMGJjXHVjOWMwIFx1YjlkMFx1YzljMFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBrPHN1Yj5pPFwvc3ViPiA9IHM8c3ViPmk8XC9zdWI+Jm1pZGRvdDthPHN1Yj5pPFwvc3ViPlx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBhJnByaW1lOzxzdWI+MTxcL3N1Yj5cdWM3NDAgWE9SXHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1Y2Q5Y1x1YjgyNVx1YWMxMiBYT1IoazxzdWI+MTxcL3N1Yj4sIC4uLiwgazxzdWI+TjxcL3N1Yj4pXHVjNzc0IFx1YjQxY1x1YjJlNC4gKGs8c3ViPjE8XC9zdWI+LCAuLi4sIGs8c3ViPk48XC9zdWI+XHVjNWQwXHVjMTFjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1ZDY0MFx1YzIxOFx1YWMxY1x1Yzc3NFx1YmE3NCBYT1IoazxzdWI+MTxcL3N1Yj4sIC4uLiwgazxzdWI+TjxcL3N1Yj4pID0gMVx1Yzc3NFx1YWNlMCwgXHVjNTQ0XHViMmM4XHViYTc0IDBcdWM3NzRcdWIyZTQpPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+YSZwcmltZTs8c3ViPjE8XC9zdWI+ID0gWE9SKGs8c3ViPjE8XC9zdWI+LCAuLi4sIGs8c3ViPk48XC9zdWI+KTxcL2xpPlxyXG5cdDxsaT5hJnByaW1lOzxzdWI+aTxcL3N1Yj4gPSBhPHN1Yj5pLTE8XC9zdWI+IGZvciAyICZsZTsgaSAmbGU7IE48XC9saT5cclxuXHQ8bGk+b3V0cHV0ID0gYTxzdWI+TjxcL3N1Yj48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2VmY2Q4MGRkLWU5MzYtNDA4Ny04OTliLTU2YjRiNDdhNTUyNVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjM0cHg7IGhlaWdodDogMzQ2cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVkMmYxIDFcdWM1ZDBcdWMxMWMgYTFcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBYT1IoMSZtaWRkb3Q7MSwgMCZtaWRkb3Q7MCwgMSZtaWRkb3Q7MSwgMSZtaWRkb3Q7MSwgMCZtaWRkb3Q7MCwgMSZtaWRkb3Q7MCwgMSZtaWRkb3Q7MSkgPSAwPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1ZDUwNFx1ZDJiOCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVhY2IwXHVhY2ZjIFx1YzkxMSBcdWNjOThcdWM3NGMgMk5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWFjMTIgc2lcdWI5N2MgXHVhY2IwXHVjODE1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkY1x1ZDUwNFx1ZDJiOCBcdWI4MDhcdWM5YzBcdWMyYTRcdWQxMzBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA3NTApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRjXHVkNTA0XHVkMmI4IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWM5MTEgXHVjYzk4XHVjNzRjIDJOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgMCBcdWI2MTBcdWIyOTQgMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMCBcdWNkOWNcdWI4MjUgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YWMxNlx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNTggXHVjMTM4XHVkMzA1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgc2lcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWMxMzhcdWQzMDVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3MDUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2hpZnQgUmVnaXN0ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcmVnaXN0ZXIgb2YgYSBjb21wdXRlciBzdG9yZXMgTiBiaXRzIGZvciBjb21wdXRhdGlvbi4gQSBzaGlmdCByZWdpc3RlciBpcyBhIHNwZWNpYWwga2luZCBvZiByZWdpc3Rlciwgd2l0aCBiaXQgdmFsdWVzIHRoYXQgY2FuIGJlIGVhc2lseSBzaGlmdGVkIGJ5IG9uZSBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+VXNpbmcgYSBmZWVkYmFjayBzaGlmdCByZWdpc3RlciwgYmluYXJ5IHBzZXVkby1yYW5kb20gbnVtYmVycyBjYW4gYmUgZ2VuZXJhdGVkIGluIHRoZSBmb2xsb3dpbmcgd2F5OiBBIHNoaWZ0IHJlZ2lzdGVyIG9mIHNpemUgTiBpcyBpbml0aWFsbHkgZmlsbGVkIHdpdGggdGhlIGJpdCB2YWx1ZXMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4gLCBhPHN1Yj5OPFwvc3ViPi4gQXQgZWFjaCBjbG9jayB0aWNrLCB0aGUgcmVnaXN0ZXIgb3V0cHV0cyB0aGUgdmFsdWUgb2YgdGhlIHJpZ2h0bW9zdCBiaXQsIGE8c3ViPk48XC9zdWI+LiBUaGUgb3RoZXIgYml0IHZhbHVlcyBhcmUgc2hpZnRlZCBieSBvbmUgcG9zaXRpb24gdG8gdGhlIHJpZ2h0LiBUaGUgZmlyc3QgcG9zaXRpb24gaXMgYXNzaWduZWQgYSBuZXcgdmFsdWUgYSZwcmltZTs8c3ViPjE8XC9zdWI+IGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwPkVhY2ggYml0IG9mIHRoZSByZWdpc3RlciBpcyBjb25uZWN0ZWQgdG8gYW4gWE9SIGdhdGUgdmlhIGEgc3dpdGNoIChzZWUgZmlndXJlIGJlbG93KS4gRm9yIGVhY2ggYml0IGkgdGhlcmUgaXMgYSBzd2l0Y2ggczxzdWI+aTxcL3N1Yj4gKHdoaWNoIGNhbiBiZSAxIG9yIDApIHRoYXQgZGV0ZXJtaW5lcyB3aGV0aGVyIHRoZSBiaXQgdmFsdWUgYWkgaXMgZm9yd2FyZGVkIG9yIG5vdCB0byB0aGUgWE9SIGdhdGUuIExldCBrPHN1Yj5pPFwvc3ViPiA9IHM8c3ViPmk8XC9zdWI+ICZtaWRkb3Q7IGE8c3ViPmk8XC9zdWI+LiBUaGUgbmV3IHZhbHVlIGEmcHJpbWU7PHN1Yj4xPFwvc3ViPiBpcyBzZXQgdG8gdGhlIG91dHB1dCB2YWx1ZSBvZiB0aGUgWE9SIGdhdGUsIFhPUihrPHN1Yj4xPFwvc3ViPiwgLi4uLCBrPHN1Yj5OPFwvc3ViPikuIChSZW1hcms6IElmIHRoZSBudW1iZXIgb2Ygb25lcyBpbiBrPHN1Yj4xPFwvc3ViPiwgLi4uLCBrPHN1Yj5OPFwvc3ViPiBpcyBvZGQsIHRoZSB2YWx1ZSBvZiBYT1IoazxzdWI+MTxcL3N1Yj4sIC4uLiwgazxzdWI+TjxcL3N1Yj4pIGlzIDEsIGVsc2UgMCkuIEJlbG93IGFyZSB0aGUgZm9ybWFsIGRlZmluaXRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmEmcHJpbWU7MSA9IFhPUihrMSwgLi4uICwga04pPFwvbGk+XHJcblx0PGxpPmEmcHJpbWU7aSA9IGFpJm1pbnVzOzEgZm9yIDIgJmxlOyBpICZsZTsgTjxcL2xpPlxyXG5cdDxsaT5vdXRwdXQgPSBhTjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZWZjZDgwZGQtZTkzNi00MDg3LTg5OWItNTZiNGI0N2E1NTI1XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MzRweDsgaGVpZ2h0OiAzNDZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGV4YW1wbGUgYWJvdmUsIHRoZSB2YWx1ZSBhPHN1Yj4xPFwvc3ViPiBhdCB0aWNrIDEgaXMgY2FsY3VsYXRlZCBhcyBmb2xsb3dzOiBYT1IoMSAmbWlkZG90OyAxLCAwICZtaWRkb3Q7IDAsIDEgJm1pZGRvdDsgMSwgMSAmbWlkZG90OyAxLCAwICZtaWRkb3Q7IDAsIDEgJm1pZGRvdDsgMCwgMSAmbWlkZG90OyAxKSA9IDAuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIGZpcnN0IDJOIG91dHB1dCB2YWx1ZXMgb2Ygc3VjaCBhIGZlZWRiYWNrIHNoaWZ0IHJlZ2lzdGVyLiBGcm9tIHRob3NlIHZhbHVlcywgeW91IHNoYWxsIHRyeSB0byBkZXRlcm1pbmUgdGhlIHN3aXRjaCB2YWx1ZXMgczxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhlIHNpemUgTiBvZiB0aGUgc2hpZnQgcmVnaXN0ZXIgKDEgJmxlOyBOICZsZTsgNzUwKS4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIDJOIG51bWJlcnMgMCBvciAxLCB3aGljaCBhcmUgdGhlIGZpcnN0IDJOIG91dHB1dCBiaXQgdmFsdWVzIG9mIHRoZSBzaGlmdCByZWdpc3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZpbGUgcmVnaXN0ZXIub3V0IGNvbnNpc3RzIG9mIGV4YWN0bHkgb25lIGxpbmUuIElmIHRoZXJlIGlzIGEgc3dpdGNoIHNldHRpbmcgdGhhdCBwcm9kdWNlcyB0aGUgZ2l2ZW4gcmVnaXN0ZXIgb3V0cHV0IHZhbHVlcywgb3V0cHV0IHRoZSBzd2l0Y2ggdmFsdWVzIHM8c3ViPmk8XC9zdWI+IG9mIGFueSBzdWNoIHN3aXRjaCBzZXR0aW5nLCBzdGFydGluZyB3aXRoIHM8c3ViPjE8XC9zdWI+LiBJZiB0aGVyZSBhcmUgbm8gc3VjaCBzd2l0Y2ggc2V0dGluZ3MsIG91dHB1dCB0aGUgbnVtYmVyIC0xIG9ubHkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2003 5번