시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 98 29 21 30.000%

문제

요즘 선풍적으로 팔리는 카드 중 하나는 앞면의 소녀시대가 새겨진 카드이다. 지원이와 항승이는 돈을 모아서 이 카드를 R*16개 사서 R*16 행렬로 나란히 정렬하여 놓았다. 그리고 평소 소녀시대에 환장하는 항승이는 모든 카드를 소녀시대가 그려져있는 앞면으로 놔둔채 흐뭇하게 감상하고 있었다.

하지만 소녀시대 중 한 멤버를 지독히 싫어하던  지원이는 그 멤버가 새겨진 카드들을 뒤집어 안 보이게하길 원하고 있다.

지원이는 카드 뒤집기 능력이 뛰어나 한 번에 가로나 세로로 연속된 카드들을 뒤집을 수 있다. 하지만 항승이가 잠시 홀려있는 상태에 있을 때 순식간에 뒤집어야하기 때문에 뒤집는 횟수를 최소한 줄이려 한다. (뒤집는 카드 수가 아닌 뒤집는 연산의 수인 것에 주의한다) 이런 지원이의 고민을 도와주자.

입력

첫 번째 줄에 카드 행의 수인 R (1 ≤ R ≤ 50)이 주어진다. 다음 R개의 줄에 길이가 16인 '0' 또는 '1'로 구성된 문자열이 주어진다. '0'은 지원이가 싫어하지 않는 멤버가 그려져 있는 카드, '1'은 지원이가 싫어하는 멤버가 그려져 있는 카드이다. 맨 처음 모든 카드는 앞면이다.

출력

지원이가 싫어하지 않는 멤버는 전부 앞면, 싫어하는 멤버는 전부 뒷면인 상태가 되게 하는 뒤집는 연산의 최소 횟수를 출력한다.

예제 입력 1

5
0000111111110000
0010000000000000
1101111111111111
0010000000000000
0000000000000000

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE2OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0YTRcdWM5ZDFcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY5NFx1Yzk5OCBcdWMxMjBcdWQ0OGRcdWM4MDFcdWM3M2NcdWI4NWMgXHVkMzE0XHViOWFjXHViMjk0IFx1Y2U3NFx1YjRkYyBcdWM5MTEgXHVkNTU4XHViMDk4XHViMjk0IFx1YzU1ZVx1YmE3NFx1Yzc1OCBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDBcdWFjMDAgXHVjMGM4XHVhY2E4XHVjOWM0IFx1Y2U3NFx1YjRkY1x1Yzc3NFx1YjJlNC4gXHVjOWMwXHVjNmQwXHVjNzc0XHVjNjQwIFx1ZDU2ZFx1YzJiOVx1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NDQgXHViYWE4XHVjNTQ0XHVjMTFjIFx1Yzc3NCBcdWNlNzRcdWI0ZGNcdWI5N2MgUioxNlx1YWMxYyBcdWMwYWNcdWMxMWMgUioxNiBcdWQ1ODlcdWI4MmNcdWI4NWMgXHViMDk4XHViNzgwXHVkNzg4IFx1YzgxNVx1YjgyY1x1ZDU1OFx1YzVlYyBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWQzYzlcdWMxOGMgXHVjMThjXHViMTQwXHVjMmRjXHViMzAwXHVjNWQwIFx1ZDY1OFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ1NmRcdWMyYjlcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDBcdWFjMDAgXHVhZGY4XHViODI0XHVjODM4XHVjNzg4XHViMjk0IFx1YzU1ZVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIxOTRcdWI0NTRcdWNjNDQgXHVkNzUwXHViYjQ3XHVkNTU4XHVhYzhjIFx1YWMxMFx1YzBjMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWMxOGNcdWIxNDBcdWMyZGNcdWIzMDAgXHVjOTExIFx1ZDU1YyBcdWJhNjRcdWJjODRcdWI5N2MgXHVjOWMwXHViM2M1XHVkNzg4IFx1YzJlYlx1YzViNFx1ZDU1OFx1YjM1OCZuYnNwOyBcdWM5YzBcdWM2ZDBcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YmE2NFx1YmM4NFx1YWMwMCBcdWMwYzhcdWFjYThcdWM5YzQgXHVjZTc0XHViNGRjXHViNGU0XHVjNzQ0IFx1YjRhNFx1YzlkMVx1YzViNCBcdWM1NDggXHViY2Y0XHVjNzc0XHVhYzhjXHVkNTU4XHVhZTM4IFx1YzZkMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YzZkMFx1Yzc3NFx1YjI5NCBcdWNlNzRcdWI0ZGMgXHViNGE0XHVjOWQxXHVhZTMwIFx1YjJhNVx1YjgyNVx1Yzc3NCBcdWI2ZjBcdWM1YjRcdWIwOTggXHVkNTVjIFx1YmM4OFx1YzVkMCBcdWFjMDBcdWI4NWNcdWIwOTggXHVjMTM4XHViODVjXHViODVjIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWNlNzRcdWI0ZGNcdWI0ZTRcdWM3NDQgXHViNGE0XHVjOWQxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWQ1NmRcdWMyYjlcdWM3NzRcdWFjMDAgXHVjN2EwXHVjMmRjIFx1ZDY0MFx1YjgyNFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWMyMWNcdWMyZGRcdWFjMDRcdWM1ZDAgXHViNGE0XHVjOWQxXHVjNWI0XHVjNTdjXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWM5MDRcdWM3NzRcdWI4MjQgXHVkNTVjXHViMmU0LiAoXHViNGE0XHVjOWQxXHViMjk0IFx1Y2U3NFx1YjRkYyBcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YjRhNFx1YzlkMVx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4XHVjNzc4IFx1YWM4M1x1YzVkMCBcdWM4ZmNcdWM3NThcdWQ1NWNcdWIyZTQpIFx1Yzc3NFx1YjdmMCBcdWM5YzBcdWM2ZDBcdWM3NzRcdWM3NTggXHVhY2UwXHViYmZjXHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkYyBcdWQ1ODlcdWM3NTggXHVjMjE4XHVjNzc4IFIgKDEgJmxlOyBSICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWUzOFx1Yzc3NFx1YWMwMCAxNlx1Yzc3OCAmIzM5OzAmIzM5OyBcdWI2MTBcdWIyOTQgJiMzOTsxJiMzOTtcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7MCYjMzk7XHVjNzQwIFx1YzljMFx1YzZkMFx1Yzc3NFx1YWMwMCBcdWMyZWJcdWM1YjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YmE2NFx1YmM4NFx1YWMwMCBcdWFkZjhcdWI4MjRcdWM4MzggXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkYywgJiMzOTsxJiMzOTtcdWM3NDAgXHVjOWMwXHVjNmQwXHVjNzc0XHVhYzAwIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWJhNjRcdWJjODRcdWFjMDAgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM3NzRcdWIyZTQuIFx1YjllOCBcdWNjOThcdWM3NGMmbmJzcDtcdWJhYThcdWI0ZTAgXHVjZTc0XHViNGRjXHViMjk0IFx1YzU1ZVx1YmE3NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5YzBcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjMmViXHVjNWI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWJhNjRcdWJjODRcdWIyOTQgXHVjODA0XHViZDgwIFx1YzU1ZVx1YmE3NCwgXHVjMmViXHVjNWI0XHVkNTU4XHViMjk0IFx1YmE2NFx1YmM4NFx1YjI5NCBcdWM4MDRcdWJkODAgXHViNGI3XHViYTc0XHVjNzc4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MThcdWFjOGMgXHVkNTU4XHViMjk0IFx1YjRhNFx1YzlkMVx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTY5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVFUFJPTSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFN0YW5rbyBlYWNoIGhhdmUgb25lIEVFUFJPTSByZWN0YW5ndWxhciBtZW1vcnkgbW9kdWxlIGNvbnNpc3Rpbmcgb2YgUiZ0aW1lczsxNiBiaXRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGV5IGFsc28gaGF2ZSB0aGUgY2lyY3VpdHJ5IG5lZWRlZCB0byB3cml0ZSBkYXRhIGludG8gdGhlIG1lbW9yeSBtb2R1bGUuIEluIG9uZSBvcGVyYXRpb24gdGhleSBjYW4gY2hhbmdlIHRoZSBzdGF0ZSBvZiBhIGNvbnRpZ3VvdXMgc2VxdWVuY2Ugb2YgYml0cyBpbiBhIHJvdyBvciBjb2x1bW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGFuZCBTdGFua28mIzM5O3MgZGFkIGFza2VkIHRoZW0gdG8gd3JpdGUgYSBwYXJ0aWN1bGFyIGFycmFuZ2VtZW50IG9mIGJpdHMgaW50byB0aGVpciBtZW1vcnkgbW9kdWxlcy4gV2hvZXZlciBpcyBmYXN0ZXIgd2lsbCBnZXQgcmVwZWF0cyBmb3IgbHVuY2ggc28gTWlya28gaXMgbG9va2luZyBmb3IgYSBwcm9ncmFtIHdoaWNoIHdpbGwgaGVscCBoaW0gd2luLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2ggd2lsbCBkZXRlcm1pbmUgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiBvcGVyYXRpb25zIG5lZWRlZCBmb3IgTWlya28gdG8gd3JpdGUgdGhlIGdpdmVuIGRhdGEgaW50byBoaXMgbWVtb3J5IG1vZHVsZS4gSW5pdGlhbGx5LCBhbGwgYml0cyBpbiB0aGUgbWVtb3J5IG1vZHVsZSBhcmUgemVyby4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgUiAoMSAmbGU7IFIgJmxlOyA1MCksIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgbW9kdWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiByb3dzIGNvbnRhaW5zIGEgc3RyaW5nIG9mIDE2IGRpZ2l0cyAmIzM5OzAmIzM5OyBvciAmIzM5OzEmIzM5OywgZGF0YSB0byBiZSB3cml0dGVuIGludG8gdGhlIG1vZHVsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBvcGVyYXRpb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Final Exam #2 1번

  • 문제를 번역한 사람: author6
  • 잘못된 번역을 찾은 사람: rdd6584