문제
김상근과 김정인이 그녀의 마음을 얻기 위해 경쟁을 벌이고 있다. 그들은 다음과 같은 방법으로 승자를 결정하기로 했다.
무한한 크기의 2차원 평면에 어떤 지점에서 그녀가 걷기 시작한다. 그리고 그녀는 상, 하, 좌, 우 4방향으로 걸어갈 수 있는데 한번 걸어갈때마다 마음이 바뀐다. 즉, 상근이를 좋아하고 있었다면 정인이를 좋아하게 되고 정인이를 좋아하고 있었다면 상근이를 좋아하게 된다. 시작점에서는 그녀가 상근이를 좋아한다고 한다. 또한 2차원 좌표판 중에는 장애물이 있는 곳이 있어서 그런 곳은 지나가지 못한다고 하자. 이때 그녀는 그 시작점에서 (0, 0)까지 장애물을 피하여 최단거리로 걸어온다고 가정한다.
그녀가 무한한 체력을 가진 것은 아니므로 그녀가 걷는 걸음수를 S걸음 이하로 제한할 때 2차원 좌표 중 최종적으로 그녀가 (0, 0)에 왔을때 상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 구하라.
출력
상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 출력하라.
예제 출력 3
복사
2500099997 2500000000
W3sicHJvYmxlbV9pZCI6IjEyMjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWIxNDBcdWM3NTggXHViOWM4XHVjNzRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlNDBcdWMwYzFcdWFkZmNcdWFjZmMgXHVhZTQwXHVjODE1XHVjNzc4XHVjNzc0IFx1YWRmOFx1YjE0MFx1Yzc1OCBcdWI5YzhcdWM3NGNcdWM3NDQgXHVjNWJiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjYmRcdWM3YzFcdWM3NDQgXHViYzhjXHVjNzc0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzJiOVx1Yzc5MFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzRcdWQ1NWNcdWQ1NWMgXHVkMDZjXHVhZTMwXHVjNzU4IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNWQwIFx1YzViNFx1YjVhNCBcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhZGY4XHViMTQwXHVhYzAwIFx1YWM3N1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjhcdWIxNDBcdWIyOTQgXHVjMGMxLCBcdWQ1NTgsIFx1Yzg4YywgXHVjNmIwIDRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVkNTVjXHViYzg4IFx1YWM3OFx1YzViNFx1YWMwOFx1YjU0Y1x1YjljOFx1YjJlNCBcdWI5YzhcdWM3NGNcdWM3NzQgXHViYzE0XHViMDEwXHViMmU0LiBcdWM5ODksIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0XHViYTc0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0XHViYTc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyZuYnNwO1x1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWFkZjhcdWIxNDBcdWFjMDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1ZDMxMCBcdWM5MTFcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YWRmOFx1YjdmMCBcdWFjZjNcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzAwXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YyBcdWFkZjhcdWIxNDBcdWIyOTQmbmJzcDtcdWFkZjggXHVjMmRjXHVjNzkxXHVjODEwXHVjNWQwXHVjMTFjICgwLCAwKVx1YWU0Y1x1YzljMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NDQgXHVkNTNjXHVkNTU4XHVjNWVjIFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWFjNzhcdWM1YjRcdWM2MjhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWIxNDBcdWFjMDAgXHViYjM0XHVkNTVjXHVkNTVjIFx1Y2NiNFx1YjgyNVx1Yzc0NCBcdWFjMDBcdWM5YzQgXHVhYzgzXHVjNzQwIFx1YzU0NFx1YjJjOFx1YmJjMFx1Yjg1YyBcdWFkZjhcdWIxNDBcdWFjMDAgXHVhYzc3XHViMjk0IFx1YWM3OFx1Yzc0Y1x1YzIxOFx1Yjk3YyBTXHVhYzc4XHVjNzRjIFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWM4MWNcdWQ1NWNcdWQ1NjAgXHViNTRjIDJcdWNjMjhcdWM2ZDAgXHVjODhjXHVkNDVjIFx1YzkxMSBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZGY4XHViMTQwXHVhYzAwICgwLCAwKVx1YzVkMCBcdWM2NTRcdWM3NDRcdWI1NGMgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWM4YyBcdWI0MjAgXHVjMmRjXHVjNzkxXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhYzhjIFx1YjQyMCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1YWMxY1x1YzIxOCBCXHVjNjQwIFx1YWM3OFx1Yzc0Y1x1YzIxOCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+KDEmbHQ7PUImbHQ7PTEwMDAwLCAxJmx0Oz1TJmx0Oz0xMDAwMDAwMCkmbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHVjNzRjIEJcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCB4LCB5XHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc0MCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuPFwvc3Bhbj48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhYzhjIFx1YjQyMCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjOGMgXHViNDIwIFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyMjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTQUJPUiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHByZXNpZGVudCBvZiB0aGUgcG9saXRpY2FsIHBhcnR5IGluIHBvd2VyIGlzIGhvbGRpbmcgYSBjb25mZXJlbmNlIGluIHRoZSBwYXJ0eSBoZWFkcXVhcnRlcnMuPFwvcD5cclxuXHJcbjxwPlBvbGl0aWNpYW5zLCBtZW1iZXJzIG9mIHRoZSBwYXJ0eSwgbGl2ZSBpbiBhIHR3by1kaW1lbnNpb25hbCBncmlkLCBvbmUgbWVtYmVyIGluIGVhY2ggY2VsbCAoZXhjZXB0IGluIGNlbGxzIGNvbnRhaW5pbmcgb2JzdGFjbGVzKS4gVGhlIGhlYWRxdWFydGVycyBhcmUgbG9jYXRlZCBpbiBjZWxsICgwLCAwKS4gVGhpcyBpcyBhbHNvIHdoZXJlIHRoZSBwcmVzaWRlbnQgb2YgdGhlIHBhcnR5IGxpdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Qb2xpdGljaWFucyBtYWtlIHN0ZXBzIGluIG9uZSBvZiB0aGUgZm91ciBkaXJlY3Rpb25zICh1cCwgZG93biwgbGVmdCwgcmlnaHQpLCBtb3ZpbmcgdG8gb25lIG9mIHRoZSBmb3VyIGFkamFjZW50IGNlbGxzIGluIG9uZSBzdGVwLiBUaGV5IGNhbiYjMzk7dCBlbnRlciBjZWxscyB3aXRoIG9ic3RhY2xlcy4gVGhlIGNvbmZlcmVuY2Ugd2lsbCBiZSBhdHRlbmRlZCBieSBhbGwgcGFydHkgbWVtYmVycyB0aGF0IGNhbiByZWFjaCBoZWFkcXVhcnRlcnMgaW4gUyBzdGVwcyBvciBsZXNzLiBFYWNoIG1lbWJlciBjb21pbmcgdG8gdGhlIGNvbmZlcmVuY2Ugd2lsbCB0YWtlIHRoZSBzaG9ydGVzdCByb3V0ZSB0byBoZWFkcXVhcnRlcnMgKG9yIGFueSBzdWNoIHJvdXRlLCBpZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHByZXNpZGVudCBoYXMgb2JzZXJ2ZWQgdGhhdCBwb2xpdGljaWFucyBjaGFuZ2UgdGhlaXIgcGFydHkgYWZmaWxpYXRpb24gd2l0aCBlYWNoIHN0ZXAgdGhleSB0YWtlLCBiZWNvbWluZyBhIG1lbWJlciBvZiB0aGUgb3RoZXIgcGFydHkgKHRoZXJlIGFyZSBvbmx5IHR3byBwYXJ0aWVzIG9uIHRoZSBwb2xpdGljYWwgc2NlbmUpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIGhvdyBtYW55IHBvbGl0aWNpYW5zIGNvbWUgdG8gdGhlIGNvbmZlcmVuY2UgYXMgbWVtYmVycyBvZiB0aGUgcGFydHkgaW4gcG93ZXIsIGFuZCBob3cgbWFueSBjb21lIGFzIG1lbWJlcnMgb2YgdGhlIG9wcG9zaW5nIHBhcnR5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIEIgYW5kIFMgKDAgJmxlOyBCICZsZTsgMTAgMDAwLCAxICZsZTsgUyAmbGU7IDEwIDAwMCAwMDApLCB0aGUgbnVtYmVyIG9mIG9ic3RhY2xlcyBhbmQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHN0ZXBzIGZyb20gdGhlIHRhc2sgZGVzY3JpcHRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBCIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBvYnN0YWNsZS4gVGhlIGFic29sdXRlIHZhbHVlIG9mIGJvdGggY29vcmRpbmF0ZXMgd2lsbCBiZSBsZXNzIHRoYW4gMTAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm8gdHdvIG9ic3RhY2xlcyB3aWxsIGJlIGluIHRoZSBzYW1lIGNlbGwgYW5kIHRoZXJlIHdpbGwgYmUgbm8gb2JzdGFjbGUgaW4gY2VsbCAoMCwgMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHR3byBpbnRlZ2VycyBvbiBhIHNpbmdsZSBsaW5lIHNlcGFyYXRlZCBieSBhIHNwYWNlLCB0aGUgbnVtYmVyIG9mIHBvbGl0aWNpYW5zIHRoYXQgY29tZSB0byB0aGUgY29uZmVyZW5jZSBhcyBtZW1iZXJzIG9mIHRoZSBwYXJ0eSBpbiBwb3dlciBhbmQgdGhlIG9wcG9zaW5nIHBhcnR5LCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==