시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NyZS5wbmdcIiBzdHlsZT1cImhlaWdodDozNjZweDsgd2lkdGg6Njg0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBcdWQyZjEgMVx1YzVkMFx1YzExYyBhMVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFhPUigxJm1pZGRvdDsxLCAwJm1pZGRvdDswLCAxJm1pZGRvdDsxLCAxJm1pZGRvdDsxLCAwJm1pZGRvdDswLCAxJm1pZGRvdDswLCAxJm1pZGRvdDsxKSA9IDA8XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVkNTA0XHVkMmI4IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yzc1OCBcdWFjYjBcdWFjZmMgXHVjOTExIFx1Y2M5OFx1Yzc0YyAyTlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YWMxMiBzaVx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHVkNTA0XHVkMmI4IFx1YjgwOFx1YzljMFx1YzJhNFx1ZDEzMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDc1MCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWQ1MDRcdWQyYjggXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwXHVjNzU4IFx1YWNiMFx1YWNmY1x1YzkxMSBcdWNjOThcdWM3NGMgMk5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCAwIFx1YjYxMFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViODA4XHVjOWMwXHVjMmE0XHVkMTMwIFx1Y2Q5Y1x1YjgyNSBcdWFjYjBcdWFjZmNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWMxMzhcdWQzMDVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBzaVx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0XHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YzEzOFx1ZDMwNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjcwNTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaGlmdCBSZWdpc3RlciIsImRlc2NyaXB0aW9uIjoiPHA+QSByZWdpc3RlciBvZiBhIGNvbXB1dGVyIHN0b3JlcyBOIGJpdHMgZm9yIGNvbXB1dGF0aW9uLiBBIHNoaWZ0IHJlZ2lzdGVyIGlzIGEgc3BlY2lhbCBraW5kIG9mIHJlZ2lzdGVyLCB3aXRoIGJpdCB2YWx1ZXMgdGhhdCBjYW4gYmUgZWFzaWx5IHNoaWZ0ZWQgYnkgb25lIHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD5Vc2luZyBhIGZlZWRiYWNrIHNoaWZ0IHJlZ2lzdGVyLCBiaW5hcnkgcHNldWRvLXJhbmRvbSBudW1iZXJzIGNhbiBiZSBnZW5lcmF0ZWQgaW4gdGhlIGZvbGxvd2luZyB3YXk6IEEgc2hpZnQgcmVnaXN0ZXIgb2Ygc2l6ZSBOIGlzIGluaXRpYWxseSBmaWxsZWQgd2l0aCB0aGUgYml0IHZhbHVlcyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiAsIGE8c3ViPk48XC9zdWI+LiBBdCBlYWNoIGNsb2NrIHRpY2ssIHRoZSByZWdpc3RlciBvdXRwdXRzIHRoZSB2YWx1ZSBvZiB0aGUgcmlnaHRtb3N0IGJpdCwgYTxzdWI+TjxcL3N1Yj4uIFRoZSBvdGhlciBiaXQgdmFsdWVzIGFyZSBzaGlmdGVkIGJ5IG9uZSBwb3NpdGlvbiB0byB0aGUgcmlnaHQuIFRoZSBmaXJzdCBwb3NpdGlvbiBpcyBhc3NpZ25lZCBhIG5ldyB2YWx1ZSBhJnByaW1lOzxzdWI+MTxcL3N1Yj4gYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHA+RWFjaCBiaXQgb2YgdGhlIHJlZ2lzdGVyIGlzIGNvbm5lY3RlZCB0byBhbiBYT1IgZ2F0ZSB2aWEgYSBzd2l0Y2ggKHNlZSBmaWd1cmUgYmVsb3cpLiBGb3IgZWFjaCBiaXQgaSB0aGVyZSBpcyBhIHN3aXRjaCBzPHN1Yj5pPFwvc3ViPiAod2hpY2ggY2FuIGJlIDEgb3IgMCkgdGhhdCBkZXRlcm1pbmVzIHdoZXRoZXIgdGhlIGJpdCB2YWx1ZSBhaSBpcyBmb3J3YXJkZWQgb3Igbm90IHRvIHRoZSBYT1IgZ2F0ZS4gTGV0IGs8c3ViPmk8XC9zdWI+ID0gczxzdWI+aTxcL3N1Yj4gJm1pZGRvdDsgYTxzdWI+aTxcL3N1Yj4uIFRoZSBuZXcgdmFsdWUgYSZwcmltZTs8c3ViPjE8XC9zdWI+IGlzIHNldCB0byB0aGUgb3V0cHV0IHZhbHVlIG9mIHRoZSBYT1IgZ2F0ZSwgWE9SKGs8c3ViPjE8XC9zdWI+LCAuLi4sIGs8c3ViPk48XC9zdWI+KS4gKFJlbWFyazogSWYgdGhlIG51bWJlciBvZiBvbmVzIGluIGs8c3ViPjE8XC9zdWI+LCAuLi4sIGs8c3ViPk48XC9zdWI+IGlzIG9kZCwgdGhlIHZhbHVlIG9mIFhPUihrPHN1Yj4xPFwvc3ViPiwgLi4uLCBrPHN1Yj5OPFwvc3ViPikgaXMgMSwgZWxzZSAwKS4gQmVsb3cgYXJlIHRoZSBmb3JtYWwgZGVmaW5pdGlvbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+YSZwcmltZTsxID0gWE9SKGsxLCAuLi4gLCBrTik8XC9saT5cclxuXHQ8bGk+YSZwcmltZTtpID0gYWkmbWludXM7MSBmb3IgMiAmbGU7IGkgJmxlOyBOPFwvbGk+XHJcblx0PGxpPm91dHB1dCA9IGFOPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zcmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzY2cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo2ODRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JbiB0aGUgZXhhbXBsZSBhYm92ZSwgdGhlIHZhbHVlIGE8c3ViPjE8XC9zdWI+IGF0IHRpY2sgMSBpcyBjYWxjdWxhdGVkIGFzIGZvbGxvd3M6IFhPUigxICZtaWRkb3Q7IDEsIDAgJm1pZGRvdDsgMCwgMSAmbWlkZG90OyAxLCAxICZtaWRkb3Q7IDEsIDAgJm1pZGRvdDsgMCwgMSAmbWlkZG90OyAwLCAxICZtaWRkb3Q7IDEpID0gMC48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgZmlyc3QgMk4gb3V0cHV0IHZhbHVlcyBvZiBzdWNoIGEgZmVlZGJhY2sgc2hpZnQgcmVnaXN0ZXIuIEZyb20gdGhvc2UgdmFsdWVzLCB5b3Ugc2hhbGwgdHJ5IHRvIGRldGVybWluZSB0aGUgc3dpdGNoIHZhbHVlcyBzPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0aGUgc2l6ZSBOIG9mIHRoZSBzaGlmdCByZWdpc3RlciAoMSAmbGU7IE4gJmxlOyA3NTApLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgMk4gbnVtYmVycyAwIG9yIDEsIHdoaWNoIGFyZSB0aGUgZmlyc3QgMk4gb3V0cHV0IGJpdCB2YWx1ZXMgb2YgdGhlIHNoaWZ0IHJlZ2lzdGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZmlsZSByZWdpc3Rlci5vdXQgY29uc2lzdHMgb2YgZXhhY3RseSBvbmUgbGluZS4gSWYgdGhlcmUgaXMgYSBzd2l0Y2ggc2V0dGluZyB0aGF0IHByb2R1Y2VzIHRoZSBnaXZlbiByZWdpc3RlciBvdXRwdXQgdmFsdWVzLCBvdXRwdXQgdGhlIHN3aXRjaCB2YWx1ZXMgczxzdWI+aTxcL3N1Yj4gb2YgYW55IHN1Y2ggc3dpdGNoIHNldHRpbmcsIHN0YXJ0aW5nIHdpdGggczxzdWI+MTxcL3N1Yj4uIElmIHRoZXJlIGFyZSBubyBzdWNoIHN3aXRjaCBzZXR0aW5ncywgb3V0cHV0IHRoZSBudW1iZXIgLTEgb25seS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=