시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB56216813333.586%

문제

길이가 같은 두 문자열 S와 T가 주어진다. S를 이루는 문자는 '0', '1', '?' 이고, T는 '0', '1' 이다. S를 T로 바꾸는데 필요한 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 다음과 같다.

  1. S의 '0'를 '1'로 바꾸기
  2. S의 '?'를 '0'이나 '1'로 바꾸기
  3. S의 두 문자의 위치를 바꾸기

예를 들어, S = "01??00"이고 T = "001010"인 경우 3번 만에 S를 T로 바꿀 수 있다.

  • S = "01??00"
  • S[2]를 '1'로 바꾼다. (S = "011?00")
  • S[3]를 '0'로 바꾼다. (S = "011000")
  • S[1]와 S[4]의 위치를 바꾼다. (S = "001010")

입력

첫째 줄에 테스트 케이스의 개수 C (C ≤ 200)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 '0', '1', '?'로 이루어진 S, 둘째 줄에는 '0', '1'로 이루어진 T가 주어진다. 두 문자열의 길이는 100을 넘지 않으며, 빈 문자열이 아니다.

출력

각 테스트 케이스마다, S를 T로 바꾸는데 필요한 연산 횟수의 최솟값을 출력한다. 만약, S를 T로 바꿀 수 없다면, -1을 출력한다.

예제 입력 1

3
01??00
001010
01
10
110001
000000

예제 출력 1

Case 1: 3
Case 2: 1
Case 3: -1
W3sicHJvYmxlbV9pZCI6IjM4MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJTXHViOTdjIFRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVjNjQwIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBTXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWJiMzhcdWM3OTBcdWIyOTQgJiMzOTswJiMzOTssICYjMzk7MSYjMzk7LCAmIzM5Oz8mIzM5OyBcdWM3NzRcdWFjZTAsIFRcdWIyOTQgJiMzOTswJiMzOTssICYjMzk7MSYjMzk7IFx1Yzc3NFx1YjJlNC4gU1x1Yjk3YyBUXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMGIwIFx1ZDY5Zlx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlNcdWM3NTggJiMzOTswJiMzOTtcdWI5N2MgJiMzOTsxJiMzOTtcdWI4NWMgXHViYzE0XHVhZmI4XHVhZTMwPFwvbGk+XHJcblx0PGxpPlNcdWM3NTggJiMzOTs/JiMzOTtcdWI5N2MgJiMzOTswJiMzOTtcdWM3NzRcdWIwOTggJiMzOTsxJiMzOTtcdWI4NWMgXHViYzE0XHVhZmI4XHVhZTMwPFwvbGk+XHJcblx0PGxpPlNcdWM3NTggXHViNDUwIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHVhZTMwPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUyA9ICZxdW90OzAxPz8wMCZxdW90O1x1Yzc3NFx1YWNlMCBUID0gJnF1b3Q7MDAxMDEwJnF1b3Q7XHVjNzc4IFx1YWNiZFx1YzZiMCAzXHViYzg4IFx1YjljY1x1YzVkMCBTXHViOTdjIFRcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UyA9ICZxdW90OzAxPz8wMCZxdW90OzxcL2xpPlxyXG5cdDxsaT5TWzJdXHViOTdjICYjMzk7MSYjMzk7XHViODVjIFx1YmMxNFx1YWZiY1x1YjJlNC4gKFMgPSAmcXVvdDswMTE/MDAmcXVvdDspPFwvbGk+XHJcblx0PGxpPlNbM11cdWI5N2MgJiMzOTswJiMzOTtcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LiAoUyA9ICZxdW90OzAxMTAwMCZxdW90Oyk8XC9saT5cclxuXHQ8bGk+U1sxXVx1YzY0MCBTWzRdXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWJjMTRcdWFmYmNcdWIyZTQuIChTID0gJnF1b3Q7MDAxMDEwJnF1b3Q7KTxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IEMgKEMgJmxlOyAyMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICYjMzk7MCYjMzk7LCAmIzM5OzEmIzM5OywgJiMzOTs/JiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFMsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTswJiMzOTssICYjMzk7MSYjMzk7XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YmU0OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBTXHViOTdjIFRcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjAgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgU1x1Yjk3YyBUXHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzgwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpdHMgRXF1YWxpemVyIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIHR3byBub24tZW1wdHkgc3RyaW5ncyBTIGFuZCBUIG9mIGVxdWFsIGxlbmd0aHMuIFMgY29udGFpbnMgdGhlIGNoYXJhY3RlcnMgJmxzcXVvOzAmcnNxdW87LCAmbHNxdW87MSZyc3F1bzsgYW5kICZsc3F1bzs/JnJzcXVvOywgd2hlcmVhcyBUIGNvbnRhaW5zICZsc3F1bzswJnJzcXVvOyBhbmQgJmxzcXVvOzEmcnNxdW87IG9ubHkuIFlvdXIgdGFzayBpcyB0byBjb252ZXJ0IFMgaW50byBUIGluIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzLiBJbiBlYWNoIG1vdmUsIHlvdSBjYW48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5jaGFuZ2UgYSAmbHNxdW87MCZyc3F1bzsgaW4gUyB0byAmbHNxdW87MSZyc3F1bzs8XC9saT5cclxuXHQ8bGk+Y2hhbmdlIGEgJmxzcXVvOz8mcnNxdW87IGluIFMgdG8gJmxzcXVvOzAmcnNxdW87IG9yICZsc3F1bzsxJnJzcXVvOzxcL2xpPlxyXG5cdDxsaT5zd2FwIGFueSB0d28gY2hhcmFjdGVycyBpbiBTPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QXMgYW4gZXhhbXBsZSwgc3VwcG9zZSBTID0gJmxkcXVvOzAxPz8wMCZyZHF1bzsgYW5kIFQgPSAmbGRxdW87MDAxMDEwJnJkcXVvOy4gV2UgY2FuIHRyYW5zZm9ybSBTIGludG8gVCBpbiAzIG1vdmVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkluaXRpYWxseSBTID0gJmxkcXVvOzAxPz8wMCZyZHF1bzs8XC9saT5cclxuXHQ8bGk+TW92ZSAxICZuZGFzaDsgY2hhbmdlIFNbMl0gdG8gJmxzcXVvOzEmcnNxdW87LiBTIGJlY29tZXMgJmxkcXVvOzAxMT8wMCZyZHF1bzs8XC9saT5cclxuXHQ8bGk+TW92ZSAyICZuZGFzaDsgY2hhbmdlIFNbM10gdG8gJmxzcXVvOzAmcnNxdW87LiBTIGJlY29tZXMgJmxkcXVvOzAxMTAwMCZyZHF1bzs8XC9saT5cclxuXHQ8bGk+TW92ZSAzICZuZGFzaDsgc3dhcCBTWzFdIHdpdGggU1s0XS4gUyBiZWNvbWVzICZsZHF1bzswMDEwMTAmcmRxdW87PFwvbGk+XHJcblx0PGxpPlMgaXMgbm93IGVxdWFsIHRvIFQ8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGlzIGFuIGludGVnZXIgQyAoQyAmbGU7IDIwMCkgdGhhdCBpbmRpY2F0ZXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgaXMgdGhlIHN0cmluZyBTIGNvbnNpc3Rpbmcgb2YgJmxzcXVvOzAmcnNxdW87LCAmbHNxdW87MSZyc3F1bzsgYW5kICZsc3F1bzs/JnJzcXVvOy4gVGhlIHNlY29uZCBsaW5lIGlzIHRoZSBzdHJpbmcgVCBjb25zaXN0aW5nIG9mICZsc3F1bzswJnJzcXVvOyBhbmQgJmxzcXVvOzEmcnNxdW87LiBUaGUgbGVuZ3RocyBvZiB0aGUgc3RyaW5ncyB3b24mcnNxdW87dCBiZSBsYXJnZXIgdGhhbiAxMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IHRoZSBjYXNlIG51bWJlciBcdWZiMDFyc3QgZm9sbG93ZWQgYnkgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIHJlcXVpcmVkIHRvIGNvbnZlcnQgUyBpbnRvIFQuIElmIHRoZSB0cmFuc2l0aW9uIGlzIGltcG9zc2libGUsIG91dHB1dCAtMSBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2012 B번