시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 71 17 15 26.786%

문제

상근이는 고등학교에 다닐 때, 친구들과 함께 아이폰으로 페이스북 게임을 했다. 그 당시에 가장 인기 있던 게임은 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 2
0110
1001
1001
0110

예제 출력 1

14

힌트

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

W3sicHJvYmxlbV9pZCI6IjI5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWJjMTUgXHViMzU4XHVjOWMwXHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNlMFx1YjRmMVx1ZDU1OVx1YWQ1MFx1YzVkMCBcdWIyZTRcdWIyZDAgXHViNTRjLCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWFjZmMgXHVkNTY4XHVhZWQ4IFx1YzU0NFx1Yzc3NFx1ZDNmMFx1YzczY1x1Yjg1YyBcdWQzOThcdWM3NzRcdWMyYTRcdWJkODEgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1YjJmOVx1YzJkY1x1YzVkMCBcdWFjMDBcdWM3YTUgXHVjNzc4XHVhZTMwIFx1Yzc4OFx1YjM1OCBcdWFjOGNcdWM3ODRcdWM3NDAgVEdOXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlMCBcdWMyMThcdWJjMTUgXHViMzU4XHVjOWMwXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWMwZGRcdWIyZDggXHViYWIwXHViNzk4IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWIyZTRcdWFjMDAgXHVhYzc4XHViOWFjXHViYTc0IFx1YzU0NFx1Yzc3NFx1ZDNmMFx1Yzc0NCBcdWJlOGZcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWMyMThcdWM1YzVcdWM3NzQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1Yzg4NVx1Yzc3NCBcdWNlNThcdWJhNzQgXHViYzE0XHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIChcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjNTQ0XHVjNzc0XHVkM2YwXHVjNzQ0IFx1YWViY1x1YjBiNFx1YjI5NCBcdWMyZGNcdWFjMDQsIFx1YzU3MVx1Yzc0NCBcdWMyZTRcdWQ1ODlcdWMyZGNcdWQwYTRcdWIyOTQgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM3NDAgXHViYWE4XHViNDUwIFx1YzVjNlx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWM3N2NcdWFkNTBcdWMyZGNcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHViYWE4XHViNDUwIFx1YzIxOFx1YmMxNVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHViMzU4XHVjOWM0XHViMmU0LiBcdWM3NzRcdWFkNTBcdWMyZGNcdWJkODBcdWQxMzAgXHViMmU0XHVjNzRjIFx1YWQ1MFx1YzJkY1x1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWM3MFx1Y2U1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjNWI0XHViNWE0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM3NzRcdWM4MDQgXHVhZDUwXHVjMmRjXHVjNWQwJm5ic3A7XHViOWRlXHVjNzQwIFx1YzIxOFx1YmMxNVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVkNjQwXHVjMjE4XHViNzdjXHViYTc0LCBcdWFkZjhcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWMyMThcdWJjMTVcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjM1OFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YmMxOFx1YjMwMFx1Yjg1YyBcdWM5ZGRcdWMyMThcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwKDBcdWIzYzQgXHVjOWRkXHVjMjE4KVx1YzVkMFx1YjI5NCBcdWMyMThcdWJjMTVcdWM3NDQgXHViNDUwIFx1YWMxY1x1YzUyOSBcdWIzNThcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWJjMThcdWM3NTggXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBIXHVhZDUwXHVjMmRjXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMjE4XHViYzE1XHVjNzc0IFx1Y2QxZCBcdWJhODcgXHViYzg4IFx1YjM1OFx1YzgzOFx1Yzg0Y1x1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YWQ1MFx1YzJkY1x1Yzc1OCBcdWMyMTggSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwLCAxICZsZTsgSCAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjZTVjXHVhZDZjXHVhZDAwXHVhY2M0XHVhYzAwIFx1ZDU4OVx1YjgyYyBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBBXHViYzg4XHVjOWY4IFx1ZDU4OVx1Yzc1OCBCXHViYzg4XHVjOWY4IFx1YzVmNFx1Yzc1OCBcdWMyMThcdWFjMDAgMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgQVx1YzY0MCBCXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YWNlMCwgMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1YWNmYyBcdWNlNWNcdWFkNmNcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgXHVkNTg5XHViODJjXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWIzMDBcdWNlNmRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBIXHVhZDUwXHVjMmRjXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YWRmOFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWIzNThcdWM5YzQgXHVjMjE4XHViYzE1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWFkNTBcdWMyZGNcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzIxOFx1YmMxNVx1Yzc0NCBcdWI0NTAgXHVhYzFjIFx1YjM1OFx1YzljNFx1YjJlNC4gMlx1YWQ1MFx1YzJkY1x1YzVkMFx1YjI5NCAxXHViYzg4LCA0XHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWMyMThcdWJjMTVcdWM3NDQgMlx1YmM4OFx1YWNmYyAzXHViYzg4XHVjNWQwXHVhYzhjIFx1YjQ1MCBcdWFjMWNcdWM1MjksIDJcdWJjODhcdWFjZmMgM1x1YmM4OFx1Yzc0MCAxXHViYzg4XHVhY2ZjIDRcdWJjODhcdWM1ZDBcdWFjOGMgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWIzNThcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibHViZW5pY2EiLCJkZXNjcmlwdGlvbiI6IjxwPkNoaWxkcmVuIGluIHNjaG9vbCBhcmUgaGF2aW5nIGZ1biBpbnN0ZWFkIG9mIGxpc3RlbmluZyB0byB0aGUgdGVhY2hlci4gV2l0aCB0aGVpciBpUGhvbmUgZGV2aWNlcyB0aGUgY2hpbGRyZW4gdGhyb3cgd2F0ZXJtZWxvbnMgYXQgZWFjaCBvdGhlciBvbiB0aGUgRmFjZWJvb2sgc29jaWFsIHNpdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIHN0YXJ0ZWQgd2hlbiBHb3JhbiB0aHJldyBvbmUgd2F0ZXJtZWxvbiBhdCBlYWNoIG9mIGhpcyBmcmllbmRzIGR1cmluZyB0aGUgZmlyc3QgY2xhc3MgdGhhdCBkYXkuIER1cmluZyBzdWJzZXF1ZW50IGNsYXNzZXMsIGFsbCBjaGlsZHJlbiAoaW5jbHVkaW5nIEdvcmFuKSBiZWhhdmVkIGxpa2UgdGhpczombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB0aGV5IGhhZCBiZWVuIGhpdCBieSBhbiBvZGQgbnVtYmVyIG9mIHdhdGVybWVsb25zIGR1cmluZyB0aGUgcHJldmlvdXMgY2xhc3MsIHRoZXkgdGhyZXcgZXhhY3RseSBvbmUgd2F0ZXJtZWxvbiBhdCBlYWNoIG9mIHRoZWlyIGZyaWVuZHM7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIHRoZXkgaGFkIGJlZW4gaGl0IGJ5IGFuIGV2ZW4gbnVtYmVyIG9mIHdhdGVybWVsb25zIChpbmNsdWRpbmcgemVybyksIHRoZW4gdGhleSBoaXQgZWFjaCBvZiB0aGVpciBmcmllbmRzIHdpdGggdHdvIHdhdGVybWVsb25zLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBjaGlsZHJlbiBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIE4sIEdvcmFuIG9idmlvdXNseSBiZWluZyBudW1iZXIgMS4gVGhlIGZyaWVuZCByZWxhdGlvbnNoaXBzIGJldHdlZW4gdGhlIGNoaWxkcmVuIGFyZSBhbHNvIGtub3duLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSB0aGUgdG90YWwgbnVtYmVyIG9mIHdhdGVybWVsb25zIHRocm93biBhZnRlciBIIGNsYXNzZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSCAoMSAmbGU7IE4gJmxlOyAyMCwgMSAmbGU7IEggJmxlOyAxMDAwMDAwIDAwMCksIHRoZSBudW1iZXIgb2Yga2lkcyBhbmQgY2xhc3Nlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzdHJpbmcgb2YgTiBjaGFyYWN0ZXJzICYjMzk7MCYjMzk7IG9yICYjMzk7MSYjMzk7LiBUaGUgY2hhcmFjdGVyIChBLCBCKSBpbiB0aGlzIG1hdHJpeCBpcyAmIzM5OzEmIzM5OyBpZiBjaGlsZHJlbiBBIGFuZCBCIGFyZSBmcmllbmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyBjaGlsZCB3aWxsIGJlIHRoZWlyIG93biBmcmllbmQuIFRoZSBpbnB1dCBtYXRyaXggd2lsbCBiZSBzeW1tZXRyaWMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygd2F0ZXJtZWxvbnMgYWZ0ZXIgSCBjbGFzc2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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