ICPC 2017 Asia Regional - Daejeon B번- Connect3 > 문제은행 : 정보올림피아드&알고리즘




3548 : Connect3

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
8 회   
시도횟수
17 회   

문제

Connect3은 잘 알려진 게임 중 하나인 Connect4를 단순화시킨 게임이다. Connect3는 2명이 하는 게임으로, 한 명은 검은 돌을, 나머지 한 명은 흰 돌을 4x4 크기의 격자판에 놓으면서 게임을 진행한다. 왼쪽 아래 격자의 좌표를 (1, 1), 오른쪽 위 격자의 좌표를 (4, 4)라고 하자. 각 플레이어는 격자의 열을 하나 선택한 뒤, 비어있는 가장 낮은 칸에 돌을 위치시킨다. 예를 들어, (3, 1)에 돌이 놓이기 위해서는 (1, 1), (2, 1)에 돌이 이미 있어야 한다. 게임은 3개의 흰색, 혹은 검은색 돌이 수평, 수직, 혹은 대각선으로 연속해 있을 때 게임이 끝나며, 그 돌을 놓은 사람이 승리한다. 게임이 끝난 이후에는 더 이상 돌을 놓을 수 없다.

 

(4, 1) (4, 2) (4, 3) (4, 4)

(3, 1) (3, 2) (3, 3) (3, 4)

(2, 1) (2, 2) (2, 3) (2, 4)

(1, 1) (1, 2) (1, 3) (1, 4)

 

 상수는 위와 같은 조건을 만족하도록 게임을 했을 때, 나올 수 있는 최종 게임판들 중 아래 조건을 만족하는 게임판들의 가짓수가 궁금했다: “게임이 가장 처음에 검은색 돌을 (1, x)에 놓으면서 시작했고, 가장 마지막 돌이 흰색이면서 (a, b)에 놓여지면서 게임이 끝난다.” 상수를 도와 게임판의 가짓수를 구해주자. 여기서 돌이 놓인 순서는 중요하지 않다는 것에 유의하자.​ 


입력형식

첫 번째 줄에 첫 번째 돌이 떨어지는 열 위치 x를 의미하는 수 x가 주어진다. 두 번째 줄에 가장 마지막 돌이 떨어진 좌표 (a, b)를 의미하는 수 a, b가 주어진다.

 


출력형식

문제의 답을 첫 번째 줄에 수 하나로 출력한다. 


입력 예

2
2 3

출력 예

516

입력 예

3
4 4

출력 예

177


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP