11084번 - 나이트의 염탐 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 311 | 123 | 89 | 38.362% |
문제
Cube World와 Baekjoon World가 한창 전쟁 중일 때 있었던 일입니다. 이 두 나라는 r행 c열의 체스판으로 생각할 수 있고, Cube World의 수도는 (1,1)에, Baekjoon World의 수도는 (r,c)에 있습니다.
Cube World에서 Baekjoon World를 염탐하기 위해서 나이트를 보낸 적이 있습니다. 나이트는 가로 또는 세로로 두 칸 이동한 뒤, 수직한 방향으로 한 칸 이동할 수 있는 날렵한 염탐꾼입니다. 나이트는 최단거리로 이동했고, 그 거리와 가짓수를 미리 조사하여 들키지 않고 성공적으로 염탐하고 왔다고 전해집니다.
두 나라가 화해한 지금, Cube World의 국왕이 Baekjoon World의 국왕에게 이 이야기를 들려주자, 둘 모두 그 거리와 가짓수가 얼마였는지 궁금해졌습니다. 위대한 과학자인 당신이 이 문제를 해결해 주세요!
입력
첫 줄에 행의 수 r과 열의 수 c가 공백을 사이에 두고 주어집니다. (1 ≤ r, c ≤ 400)
출력
첫 줄에 나이트가 이동한 거리와 그 가짓수를 공백을 사이에 두고 출력합니다. 가짓수가 너무 클 수 있으므로, 1 000 000 009로 나눈 나머지를 출력합니다.
만약 나이트가 국왕을 속였다면, 나이트의 목숨은 없기 때문에 None만 출력합니다.
예제 입력 1
4 4
예제 출력 1
2 2
예제 입력 2
4 5
예제 출력 2
3 1
예제 입력 3
2 4
예제 출력 3
None
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호