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

문제

상근이는 고등학교에 다닐 때, 친구들과 함께 아이폰으로 페이스북 게임을 했다. 그 당시에 가장 인기 있던 게임은 TGN에서 만든 수박 던지기이다.

선생님 몰래 게임을 하다가 걸리면 아이폰을 뺏길 수 있기 때문에, 그들은 수업이 시작하는 종이 치면 바로 게임을 한다. (게임을 하는데 드는 시간과 아이폰을 꺼내는 시간, 앱을 실행시키는 시간과 같은 시간은 모두 없다)

게임은 항상 상근이가 시작한다. 일교시가 시작할 때, 상근이는 그들의 친구에게 모두 수박을 하나씩 던진다. 이교시부터 다음 교시가 시작할 때는 다음과 같은 과정을 거치게 된다.

만약, 어떤 학생이 이전 교시에 맞은 수박의 수가 홀수라면, 그는 모든 친구에게 수박을 하나씩 던진다. 이와 반대로 짝수개인 경우(0도 짝수)에는 수박을 두 개씩 던진다.

상근이네 반의 모든 학생들은 1번부터 N번까지 번호가 매겨져 있다. 상근이는 1번이다.

학생들의 친구 관계가 주어졌을 때, H교시가 끝난 이후에 수박이 총 몇 번 던져졌는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 N과 교시의 수 H가 주어진다. (1 ≤ N ≤ 20, 1 ≤ H ≤ 1,000,000,000)

다음 N개 줄에는 학생들의 친구관계가 행렬 형식으로 주어진다. A번째 행의 B번째 열의 수가 1인 경우에는 A와 B가 친구이고, 0인 경우에는 친구가 아니다.

자기 자신과 친구인 경우는 없고, 행렬은 항상 대칭이다.

출력

첫째 줄에 H교시가 끝난 이후에 학생들이 그때까지 던진 수박의 수를 출력한다.

예제 입력 1

4 1
0110
1001
1001
0110

예제 출력 1

2

예제 입력 2

4 2
0110
1001
1001
0110

예제 출력 2

14

예제 입력 3

5 3
01000
10110
01000
01001
00010

예제 출력 3

26

힌트

두 번째 예제의 경우, 1교시가 시작할 때 상근이는 수박을 두 개 던진다. 2교시에는 1번, 4번 학생은 수박을 2번과 3번에게 두 개씩, 2번과 3번은 1번과 4번에게 한 개씩 던진다.

W3sicHJvYmxlbV9pZCI6IjI5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWJjMTUgXHViMzU4XHVjOWMwXHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YjRmMVx1ZDU1OVx1YWQ1MFx1YzVkMCBcdWIyZTRcdWIyZDAgXHViNTRjLCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWFjZmMgXHVkNTY4XHVhZWQ4IFx1YzU0NFx1Yzc3NFx1ZDNmMFx1YzczY1x1Yjg1YyBcdWQzOThcdWM3NzRcdWMyYTRcdWJkODEgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1YjJmOVx1YzJkY1x1YzVkMCBcdWFjMDBcdWM3YTUgXHVjNzc4XHVhZTMwIFx1Yzc4OFx1YjM1OCBcdWFjOGNcdWM3ODRcdWM3NDAgVEdOXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlMCBcdWMyMThcdWJjMTUgXHViMzU4XHVjOWMwXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWMwZGRcdWIyZDggXHViYWIwXHViNzk4IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWIyZTRcdWFjMDAgXHVhYzc4XHViOWFjXHViYTc0IFx1YzU0NFx1Yzc3NFx1ZDNmMFx1Yzc0NCBcdWJlOGZcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWMyMThcdWM1YzVcdWM3NzQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1Yzg4NVx1Yzc3NCBcdWNlNThcdWJhNzQgXHViYzE0XHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIChcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjNTQ0XHVjNzc0XHVkM2YwXHVjNzQ0IFx1YWViY1x1YjBiNFx1YjI5NCBcdWMyZGNcdWFjMDQsIFx1YzU3MVx1Yzc0NCBcdWMyZTRcdWQ1ODlcdWMyZGNcdWQwYTRcdWIyOTQgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzVjNlx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWM3N2NcdWFkNTBcdWMyZGNcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHViYWE4XHViNDUwIFx1YzIxOFx1YmMxNVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHViMzU4XHVjOWM0XHViMmU0LiBcdWM3NzRcdWFkNTBcdWMyZGNcdWJkODBcdWQxMzAgXHViMmU0XHVjNzRjIFx1YWQ1MFx1YzJkY1x1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWM3MFx1Y2U1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM3NzRcdWM4MDQgXHVhZDUwXHVjMmRjXHVjNWQwJm5ic3A7XHViOWRlXHVjNzQwIFx1YzIxOFx1YmMxNVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVkNjQwXHVjMjE4XHViNzdjXHViYTc0LCBcdWFkZjhcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWMyMThcdWJjMTVcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjM1OFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWM5ZGRcdWMyMThcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwKDBcdWIzYzQgXHVjOWRkXHVjMjE4KVx1YzVkMFx1YjI5NCBcdWMyMThcdWJjMTVcdWM3NDQgXHViNDUwIFx1YWMxY1x1YzUyOSBcdWIzNThcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWJjMThcdWM3NTggXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBIXHVhZDUwXHVjMmRjXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMjE4XHViYzE1XHVjNzc0IFx1Y2QxZCBcdWJhODcgXHViYzg4IFx1YjM1OFx1YzgzOFx1Yzg0Y1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YWQ1MFx1YzJkY1x1Yzc1OCBcdWMyMTggSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwLCAxICZsZTsgSCAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjXHVhZDAwXHVhY2M0XHVhYzAwIFx1ZDU4OVx1YjgyYyBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBBXHViYzg4XHVjOWY4IFx1ZDU4OVx1Yzc1OCBCXHViYzg4XHVjOWY4IFx1YzVmNFx1Yzc1OCBcdWMyMThcdWFjMDAgMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YWNlMCwgMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWNlNWNcdWFkNmNcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgXHVkNTg5XHViODJjXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWIzMDBcdWNlNmRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBIXHVhZDUwXHVjMmRjXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YWRmOFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWIzNThcdWM5YzQgXHVjMjE4XHViYzE1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCwgMVx1YWQ1MFx1YzJkY1x1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMyMThcdWJjMTVcdWM3NDQgXHViNDUwIFx1YWMxYyBcdWIzNThcdWM5YzRcdWIyZTQuIDJcdWFkNTBcdWMyZGNcdWM1ZDBcdWIyOTQgMVx1YmM4OCwgNFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjMjE4XHViYzE1XHVjNzQ0IDJcdWJjODhcdWFjZmMgM1x1YmM4OFx1YzVkMFx1YWM4YyBcdWI0NTAgXHVhYzFjXHVjNTI5LCAyXHViYzg4XHVhY2ZjIDNcdWJjODhcdWM3NDAgMVx1YmM4OFx1YWNmYyA0XHViYzg4XHVjNWQwXHVhYzhjIFx1ZDU1YyBcdWFjMWNcdWM1MjkgXHViMzU4XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Imx1YmVuaWNhIiwiZGVzY3JpcHRpb24iOiI8cD5DaGlsZHJlbiBpbiBzY2hvb2wgYXJlIGhhdmluZyBmdW4gaW5zdGVhZCBvZiBsaXN0ZW5pbmcgdG8gdGhlIHRlYWNoZXIuIFdpdGggdGhlaXIgaVBob25lIGRldmljZXMgdGhlIGNoaWxkcmVuIHRocm93IHdhdGVybWVsb25zIGF0IGVhY2ggb3RoZXIgb24gdGhlIEZhY2Vib29rIHNvY2lhbCBzaXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBzdGFydGVkIHdoZW4gR29yYW4gdGhyZXcgb25lIHdhdGVybWVsb24gYXQgZWFjaCBvZiBoaXMgZnJpZW5kcyBkdXJpbmcgdGhlIGZpcnN0IGNsYXNzIHRoYXQgZGF5LiBEdXJpbmcgc3Vic2VxdWVudCBjbGFzc2VzLCBhbGwgY2hpbGRyZW4gKGluY2x1ZGluZyBHb3JhbikgYmVoYXZlZCBsaWtlIHRoaXM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgdGhleSBoYWQgYmVlbiBoaXQgYnkgYW4gb2RkIG51bWJlciBvZiB3YXRlcm1lbG9ucyBkdXJpbmcgdGhlIHByZXZpb3VzIGNsYXNzLCB0aGV5IHRocmV3IGV4YWN0bHkgb25lIHdhdGVybWVsb24gYXQgZWFjaCBvZiB0aGVpciBmcmllbmRzOyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiB0aGV5IGhhZCBiZWVuIGhpdCBieSBhbiBldmVuIG51bWJlciBvZiB3YXRlcm1lbG9ucyAoaW5jbHVkaW5nIHplcm8pLCB0aGVuIHRoZXkgaGl0IGVhY2ggb2YgdGhlaXIgZnJpZW5kcyB3aXRoIHR3byB3YXRlcm1lbG9ucy4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgY2hpbGRyZW4gYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBOLCBHb3JhbiBvYnZpb3VzbHkgYmVpbmcgbnVtYmVyIDEuIFRoZSBmcmllbmQgcmVsYXRpb25zaGlwcyBiZXR3ZWVuIHRoZSBjaGlsZHJlbiBhcmUgYWxzbyBrbm93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIHRvdGFsIG51bWJlciBvZiB3YXRlcm1lbG9ucyB0aHJvd24gYWZ0ZXIgSCBjbGFzc2VzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEggKDEgJmxlOyBOICZsZTsgMjAsIDEgJmxlOyBIICZsZTsgMTAwMDAwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGtpZHMgYW5kIGNsYXNzZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGEgc3RyaW5nIG9mIE4gY2hhcmFjdGVycyAmIzM5OzAmIzM5OyBvciAmIzM5OzEmIzM5Oy4gVGhlIGNoYXJhY3RlciAoQSwgQikgaW4gdGhpcyBtYXRyaXggaXMgJiMzOTsxJiMzOTsgaWYgY2hpbGRyZW4gQSBhbmQgQiBhcmUgZnJpZW5kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm8gY2hpbGQgd2lsbCBiZSB0aGVpciBvd24gZnJpZW5kLiBUaGUgaW5wdXQgbWF0cml4IHdpbGwgYmUgc3ltbWV0cmljLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHdhdGVybWVsb25zIGFmdGVyIEggY2xhc3Nlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBzZWNvbmQgZXhhbXBsZSwgR29yYW4gdGhyb3dzIHR3byB3YXRlcm1lbG9ucyBkdXJpbmcgdGhlIGZpcnN0IGNsYXNzLiBEdXJpbmcgdGhlIHNlY29uZCBjbGFzcywgY2hpbGRyZW4gMSBhbmQgNCBlYWNoIHRocm93IHR3byB3YXRlcm1lbG9ucyBhdCAyIGFuZCAzIGVhY2gsIHdoaWxlIDIgYW5kIDMgdGhyb3cgb25lIHdhdGVybWVsb24gYXQgMSBhbmQgNC4gQSB0b3RhbCBvZiAxMiB3YXRlcm1lbG9ucyBpcyB0aHJvd24gZHVyaW5nIHRoZSBzZWNvbmQgY2xhc3MuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #5 4번

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