시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB34171553.571%

문제

상근이의 집에는 전구가 L개 있다. 각 전구를 켜고 끌 수 있는 스위치는 일렬로 늘어서있다. 전구가 켜진 상태에서 스위치를 누르면 꺼지고, 꺼진 상태에서 누르면 켜진다.

매일 밤, 잠을 자기 전에 상근이는 전구를 모두 끈다. 모든 스위치를 한 번씩 눌러 전구를 끄는 일은 시간이 오래걸린다.

불을 켜고 끄는 일을 조금 더 편하게 하기 위해 상근이는 스위치를 편하게 누를 수 있는 장치를 발명했다. 장치는 T개의 슬롯이 일렬로 놓여져있다. 일부 슬롯에는 스위치 버튼을 누를 수 있는 막대가 꽂혀있고, 나머지 슬롯은 비어있다. 예를 들어, 장치에 슬롯이 4개 있고, 1, 2, 4번째 슬롯에 막대가 꽂혀있으면, 이를 '1101'로 표현할 수 있다.

위의 장치로 L개의 스위치 중 가장 왼쪽 스위치를 누르면, 1, 2, 4번 스위치를 누를 수 있고, 그 전구의 상태가 변하게 된다. 3번 슬롯은 비어있기 때문에, 3번 전구는 변하지 않는다. 즉, 가장 왼쪽에 있는 슬롯을 기준으로 i번째 스위치를 누른다면 i, i+1, ..., i+T-1번째 스위치 중 막대가 꽂힌 슬롯에 대응되는 스위치의 전구가 변하게 된다. 단, T개의 모든 슬롯이 스위치와 대응되어야 한다. 즉, 스위치 바깥으로 슬롯이 나가면 안 된다.

현재 스위치의 상태와 상근이가 발명한 슬롯의 상태가 주어졌을 때, 불이 켜진 상태를 최소로 하려면 장치로 슬롯을 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L (3 ≤ L ≤ 50)과 T (1 ≤ T ≤ 7)가 주어진다. 다음 줄에 길이가 L인 문자열이 주어진다. 1은 i번째 전구가 켜진 상태, 0은 꺼진 상태이다. 세 번째 줄에는 길이가 T인 문자열이 주어진다. 0은 빈 슬롯, 1은 막대가 꽂힌 슬롯이다.

출력

첫째 줄에 최소의 불이 켜진 상태를 만들기 위해 슬롯으로 눌러야할 등불 순서의 개수 K를 출력한다. 그 다음 K줄에는 눌러야 하는 스위치를 순서대로 출력한다. 슬롯으로 누르는 가장 왼쪽 스위치의 번호를 출력한다. (장치를 회전시킬 수는 없다) K는 1000보다 작거나 같아야 한다.

예제 입력 1

10 4
1111111111
1101

예제 출력 1

5
3
1
4
7
6

힌트

  • 1111111111  초기 상태
  • 1100101111  3-6번 불을 슬롯으로 누른 후
  • 0001101111  1-4번 불을 슬롯으로 누른 후
  • 0000000111  4-7번 불을 슬롯으로 누른 후
  • 0000001010  7-10번 불을 슬롯으로 누른 후
  • 0000010000  6-9번 불을 슬롯으로 누른 후

최종 1개의 불이 켜진 상태가 되고 모든 불을 끄는 해는 존재하지 않는다.

W3sicHJvYmxlbV9pZCI6IjE4MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODhcdWIwNDRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVjODA0XHVhZDZjXHVhYzAwIExcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjODA0XHVhZDZjXHViOTdjIFx1Y2YxY1x1YWNlMCBcdWIwNGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWIyOTQgXHVjNzdjXHViODJjXHViODVjIFx1YjI5OFx1YzViNFx1YzExY1x1Yzc4OFx1YjJlNC4gXHVjODA0XHVhZDZjXHVhYzAwIFx1Y2YxY1x1YzljNCBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWFlYmNcdWM5YzBcdWFjZTAsIFx1YWViY1x1YzljNCBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMgXHViMjA0XHViOTc0XHViYTc0IFx1Y2YxY1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHVjNzdjIFx1YmMyNCwgXHVjN2EwXHVjNzQ0IFx1Yzc5MFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgwNFx1YWQ2Y1x1Yjk3YyBcdWJhYThcdWI0NTAgXHViMDQ4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViMjBjXHViN2VjIFx1YzgwNFx1YWQ2Y1x1Yjk3YyBcdWIwNDRcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM2MjRcdWI3OThcdWFjNzhcdWI5YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4OFx1Yzc0NCBcdWNmMWNcdWFjZTAgXHViMDQ0XHViMjk0IFx1Yzc3Y1x1Yzc0NCBcdWM4NzBcdWFlMDggXHViMzU0IFx1ZDNiOFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0Jm5ic3A7XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWQzYjhcdWQ1NThcdWFjOGMgXHViMjA0XHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjN2E1XHVjZTU4XHViOTdjIFx1YmMxY1x1YmE4NVx1ZDU4OFx1YjJlNC4gXHVjN2E1XHVjZTU4XHViMjk0IFRcdWFjMWNcdWM3NTggXHVjMmFjXHViODZmXHVjNzc0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzhcdWM3ODhcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWMyYWNcdWI4NmZcdWM1ZDBcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI5YzlcdWIzMDBcdWFjMDAgXHVhZjQyXHVkNjAwXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjMmFjXHViODZmXHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjN2E1XHVjZTU4XHVjNWQwIFx1YzJhY1x1Yjg2Zlx1Yzc3NCA0XHVhYzFjIFx1Yzc4OFx1YWNlMCwgMSwgMiwgNFx1YmM4OFx1YzlmOCBcdWMyYWNcdWI4NmZcdWM1ZDAgXHViOWM5XHViMzAwXHVhYzAwIFx1YWY0Mlx1ZDYwMFx1Yzc4OFx1YzczY1x1YmE3NCwgXHVjNzc0XHViOTdjICYjMzk7MTEwMSYjMzk7XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjN2E1XHVjZTU4XHViODVjIExcdWFjMWNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIyMDRcdWI5NzRcdWJhNzQsIDEsIDIsIDRcdWJjODggXHVjMmE0XHVjNzA0XHVjZTU4XHViOTdjIFx1YjIwNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFkZjggXHVjODA0XHVhZDZjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWJjYzBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiAzXHViYzg4IFx1YzJhY1x1Yjg2Zlx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCAzXHViYzg4IFx1YzgwNFx1YWQ2Y1x1YjI5NCBcdWJjYzBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM5ODksIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhY1x1Yjg2Zlx1Yzc0NCBcdWFlMzBcdWM5MDBcdWM3M2NcdWI4NWMgaVx1YmM4OFx1YzlmOCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHViMjA0XHViOTc4XHViMmU0XHViYTc0IGksIGkrMSwgLi4uLCBpK1QtMVx1YmM4OFx1YzlmOCBcdWMyYTRcdWM3MDRcdWNlNTggXHVjOTExIFx1YjljOVx1YjMwMFx1YWMwMCBcdWFmNDJcdWQ3OGMgXHVjMmFjXHViODZmXHVjNWQwIFx1YjMwMFx1Yzc1MVx1YjQxOFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHVjODA0XHVhZDZjXHVhYzAwIFx1YmNjMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjJlOCwgVFx1YWMxY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjMmFjXHViODZmXHVjNzc0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWIzMDBcdWM3NTFcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWJjMTRcdWFlNjVcdWM3M2NcdWI4NWMgXHVjMmFjXHViODZmXHVjNzc0IFx1YjA5OFx1YWMwMFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YzY0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViYzFjXHViYTg1XHVkNTVjIFx1YzJhY1x1Yjg2Zlx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViZDg4XHVjNzc0IFx1Y2YxY1x1YzljNCBcdWMwYzFcdWQwZGNcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM3YTVcdWNlNThcdWI4NWMgXHVjMmFjXHViODZmXHVjNzQ0IFx1YmE4NyBcdWJjODggXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTCAoMyAmbGU7IEwgJmxlOyA1MClcdWFjZmMgVCAoMSAmbGU7IFQgJmxlOyA3KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVhZTM4XHVjNzc0XHVhYzAwIExcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMVx1Yzc0MCBpXHViYzg4XHVjOWY4IFx1YzgwNFx1YWQ2Y1x1YWMwMCBcdWNmMWNcdWM5YzQgXHVjMGMxXHVkMGRjLCAwXHVjNzQwIFx1YWViY1x1YzljNCBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBUXHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDBcdWM3NDAgXHViZTQ4IFx1YzJhY1x1Yjg2ZiwgMVx1Yzc0MCBcdWI5YzlcdWIzMDBcdWFjMDAgXHVhZjQyXHVkNzhjIFx1YzJhY1x1Yjg2Zlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWJkODhcdWM3NzQgXHVjZjFjXHVjOWM0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzJhY1x1Yjg2Zlx1YzczY1x1Yjg1YyBcdWIyMGNcdWI3ZWNcdWM1N2NcdWQ1NjAgXHViNGYxXHViZDg4IFx1YzIxY1x1YzExY1x1Yzc1OCBcdWFjMWNcdWMyMTggS1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgS1x1YzkwNFx1YzVkMFx1YjI5NCBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMyYWNcdWI4NmZcdWM3M2NcdWI4NWMgXHViMjA0XHViOTc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjMmE0XHVjNzA0XHVjZTU4XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWM3YTVcdWNlNThcdWI5N2MgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGFjIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQpIEtcdWIyOTQgMTAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHVsPlxyXG5cdDxsaT48Y29kZT4xMTExMTExMTExPFwvY29kZT4mbmJzcDsgXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkYzxcL2xpPlxyXG5cdDxsaT48Y29kZT4xMTAwMTAxMTExPFwvY29kZT4mbmJzcDsgMy02XHViYzg4IFx1YmQ4OFx1Yzc0NCBcdWMyYWNcdWI4NmZcdWM3M2NcdWI4NWMgXHViMjA0XHViOTc4IFx1ZDZjNDxcL2xpPlxyXG5cdDxsaT48Y29kZT4wMDAxMTAxMTExPFwvY29kZT4mbmJzcDsgMS00XHViYzg4IFx1YmQ4OFx1Yzc0NCBcdWMyYWNcdWI4NmZcdWM3M2NcdWI4NWMgXHViMjA0XHViOTc4IFx1ZDZjNDxcL2xpPlxyXG5cdDxsaT48Y29kZT4wMDAwMDAwMTExPFwvY29kZT4mbmJzcDsgNC03XHViYzg4IFx1YmQ4OFx1Yzc0NCBcdWMyYWNcdWI4NmZcdWM3M2NcdWI4NWMgXHViMjA0XHViOTc4IFx1ZDZjNDxcL2xpPlxyXG5cdDxsaT48Y29kZT4wMDAwMDAxMDEwPFwvY29kZT4mbmJzcDsgNy0xMFx1YmM4OCBcdWJkODhcdWM3NDQgXHVjMmFjXHViODZmXHVjNzNjXHViODVjIFx1YjIwNFx1Yjk3OCBcdWQ2YzQ8XC9saT5cclxuXHQ8bGk+PGNvZGU+MDAwMDAxMDAwMDxcL2NvZGU+Jm5ic3A7IDYtOVx1YmM4OCBcdWJkODhcdWM3NDQgXHVjMmFjXHViODZmXHVjNzNjXHViODVjIFx1YjIwNFx1Yjk3OCBcdWQ2YzQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWNkNWNcdWM4ODUgMVx1YWMxY1x1Yzc1OCBcdWJkODhcdWM3NzQgXHVjZjFjXHVjOWM0IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MThcdWFjZTAgXHViYWE4XHViNGUwIFx1YmQ4OFx1Yzc0NCBcdWIwNDRcdWIyOTQgXHVkNTc0XHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGlnaHRzIE91dCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNvd3Mgc28gbXVjaCBwcmVmZXIgdG8gc2xlZXAgaW4gdGhlIGRhcmsuIEV2ZXJ5IG5pZ2h0LCB0aG91Z2gsIHdoZW4gdGhleSByZXR1cm4gdG8gdGhlIGJhcm4sIHNvbWUgb2YgdGhlIEwgKDMgJmx0Oz0gTCAmbHQ7PSA1MCkgbGlnaHRzIGFyZSBzd2l0Y2hlZCBvbi4gVGhleSBrbm93IHRoZSBsb2NhdGlvbiBvZiB0aGUgcHVzaCBidXR0b24gc3dpdGNoZXMgYnV0LCBhcyBpcyBhbHdheXMgdGhlIHByb2JsZW0sIHRoZXkgbGFjayBmaW5nZXJzLiBUaGUgYnV0dG9ucyBhcmUgYXJyYW5nZWQgaW4gYSBuaWNlIHJvdywgYW5kIHRoZSBsZWZ0IG1vc3QgYnV0dG9uICgjMSkgdG9nZ2xlcyBsaWdodCAjMTsgdGhlIG5leHQgYnV0dG9uIHRvIHRoZSByaWdodCB0b2dnbGVzIGxpZ2h0ICMyOyBhbmQgc28gb24uICgmIzM5O1RvZ2dsZSYjMzk7IG1lYW5zIGNoYW5nZSBmcm9tIG9mZi10by1vbiBvciBvbi10by1vZmYsIGRlcGVuZGluZyBvbiB0aGUgY3VycmVudCBzdGF0ZSBvZiB0aGUgc3dpdGNoLik8XC9wPlxyXG5cclxuPHA+VGhleSBkbyBob3dldmVyIGhhdmUgYW4gdW51c3VhbCBwaXRjaGZvcmsgd2l0aCBUICgxICZsdDs9IFQgJmx0Oz0gNykgc2xvdHMsIGVhY2ggb25lIG9mIHdoaWNoIG1pZ2h0IGhvbGQgYSB0aW5lIHRoYXQgY2FuIHB1c2ggdGhlIHN3aXRjaGVzLiBTb21lIHRpbmVzIGFyZSBwcmVzZW50OyBzb21lIG1pZ2h0IGJlIGFic2VudC4gQnkgd2F5IG9mIGV4YW1wbGUsIGltYWdpbmUgYSBwaXRjaGZvcmsgd2l0aCBUPTQgYW5kIGEgbWlzc2luZyB0aW5lLiBUaGlzIHBhcnRpY3VsYXIgcGl0Y2hmb3JrIGhhcyB0aW5lcyBpbiB0aGUgMXN0LCAybmQsIGFuZCA0dGggcG9zaXRpb25zLCBlYXNpbHkgZGVzY3JpYmVkIGFzICYjMzk7MTEwMSYjMzk7LjxcL3A+XHJcblxyXG48cD5JZiB0aGUgcGl0Y2hmb3JrIGlzIGFpbWVkIGF0IHRoZSBsZWZ0bW9zdCBzd2l0Y2gsIHRoZW4gbGlnaHRzICMxLCAjMiwgYW5kICM0IGFyZSB0b2dnbGVkICgjMyBpc24mIzM5O3QgdG9nZ2xlZCBzaW5jZSB0aGVyZSBpcyBubyB0aW5lIHRoZXJlKS4gSWYgdGhlIHBpdGNoZm9yayBpcyBhaW1lZCBhdCBzd2l0Y2ggIzMsIHRoZW4gbGlnaHRzICMzLCAjNCwgYW5kICM2IGFyZSB0b2dnbGVkLiBUaGUgcGl0Y2hmb3JrIG11c3QgYmUgYWltZWQgc28gdGhhdCBhbGwgaXRzIHRpbmUgc2xvdHMgdG91Y2ggc3dpdGNoZXM7IHRoZSBmb3JrIGNhbm5vdCBjcm9zcyB0aGUgZW5kIG9mIHRoZSBsaW5lIG9mIHN3aXRjaGVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGxpc3Qgb2YgbGlnaHRzIHRoYXQgYXJlIG9uIGFuZCBhIGNvbmZpZ3VyYXRpb24gZm9yIGEgcGl0Y2hmb3JrLCBkZXRlcm1pbmUgYSBzZXF1ZW5jZSBvZiBwaXRjaGZvcmsgcHJlc3NlcyB0aGF0IHdpbGwgdG9nZ2xlIHRoZSBsaWdodHMgdW50aWwgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGxpZ2h0cyBpcyBsaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTCBhbmQgVDxcL3A+XHJcblxyXG48cD4qIExpbmUgMjogQSBsaW5lIHdpdGggTCBjaGFyYWN0ZXJzIChhbmQgbm8gc3BhY2VzKSwgZWFjaCBvZiB3aGljaCBpcyAmIzM5OzAmIzM5OyBvciAmIzM5OzEmIzM5Oy4gJiMzOTsxJiMzOTsgbWVhbnMgYSBsaWdodCBpbiB0aGF0IHNsb3QgaXMgbGl0OyAmIzM5OzAmIzM5OyBtZWFucyB0aGUgbGlnaHQgaW4gdGhhdCBzbG90IGlzIG5vdCBsaXQuPFwvcD5cclxuXHJcbjxwPiogTGluZSAzOiBBIGxpbmUgd2l0aCBUIGNoYXJhY3RlcnMsIGVhY2ggb2Ygd2hpY2ggaXMgJiMzOTswJiMzOTsgb3IgJiMzOTsxJiMzOTsgKG5vIHNwYWNlcyBhcmUgcHJlc2VudCkuICYjMzk7MSYjMzk7IG1lYW5zIGEgdGluZSBpcyBwcmVzZW50IG9uIHRoZSBwaXRjaGZvcmsgaW4gdGhhdCBzbG90OyAmIzM5OzAmIzM5OyBtZWFucyBvdGhlcndpc2UuICZuYnNwO1RoZSBwaXRjaGZvcmsgY2FuIG5vdCBiZSBpbnZlcnRlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogSywgdGhlIG51bWJlciBvZiBwb3NpdGlvbnMgYXQgd2hpY2ggdGhlIHBpdGNoZm9yayB3YXMgYWltZWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD4xMTExMTExMTExICZuYnNwO1N0YXJ0PGJyIFwvPlxyXG4xMTAwMTAxMTExICZuYnNwO1RvZ2dsZSAzPGJyIFwvPlxyXG4wMDAxMTAxMTExICZuYnNwO1RvZ2dsZSAxPGJyIFwvPlxyXG4wMDAwMDAwMTExICZuYnNwO1RvZ2dsZSA0PGJyIFwvPlxyXG4wMDAwMDAxMDEwICZuYnNwO1RvZ2dsZSA3PGJyIFwvPlxyXG4wMDAwMDEwMDAwICZuYnNwO1RvZ2dsZSA2PFwvcD5cclxuXHJcbjxwPk9uZSBsaWdodCByZW1haW5pbmcgaXMgdGhlIGJlc3Qgb25lIGNhbiBkby4gJm5ic3A7TWFueSBvdGhlciBzb2x1dGlvbnMgd2lsbCBsZWF2ZSBvbmUgbGlnaHQgbGl0IChwb3NzaWJseSBhIGRpZmZlcmVudCBsaWdodCkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO March 2006 Contest > Silver 1번