셜록과 괄호 (라지)

면접 대비

시간 제한5초메모리 제한512 MB

요약

여는 괄호 L개와 닫는 괄호 R개로 길이 L+R인 문자열을 만들 때, 비어 있지 않은 균형 잡힌 부분 문자열의 개수를 최대로 하고 그 값을 구한다.

난이도: 보통10점 중 6점
유형: 문자열, 그리디, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

셜록과 왓슨은 프로그래밍 수업에서 균형 잡힌 괄호 문자열을 배웠다. (와 )로만 이루어진 문자열 $S$ 는 다음 중 하나를 만족할 때 균형 잡힌 문자열이다.

$S$ 가 빈 문자열이다.
$S$ 가 ( $A$ ) 꼴이고, $A$ 가 균형 잡힌 문자열이다.
$S$ 가 균형 잡힌 두 문자열 $A$ 와 $B$ 를 이어 붙인 $AB$ 꼴이다.

셜록이 금방 답을 내놓고 자랑하자, 왓슨은 다음 문제를 냈다. 여는 괄호 (가 정확히 $L$ 개, 닫는 괄호 )가 정확히 $R$ 개인 길이 $L + R$ 의 문자열 $S$ 를 만들되, 비어 있지 않은 균형 잡힌 부분 문자열의 개수를 최대로 하라는 것이다. 시작 위치나 끝 위치가 다르면 내용이 같아도 서로 다른 부분 문자열로 센다. $S$ 자체는 균형 잡히지 않아도 된다.

셜록은 최댓값만 알면 문자열도 직접 만들 수 있다고 한다. $L$ 과 $R$ 이 주어질 때 비어 있지 않은 균형 잡힌 부분 문자열 개수의 최댓값을 구하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 줄에 각각 두 정수 $L$ 과 $R$ 이 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 구한 최댓값이다.

제한

$1 \le T \le 100$
$0 \le L \le 10^5$
$0 \le R \le 10^5$
$1 \le L + R \le 10^5$

설명

$L = 1$ , $R = 0$ 이면 만들 수 있는 문자열은 ( 하나뿐이고, 비어 있지 않은 균형 잡힌 부분 문자열은 없다.

$L = 1$ , $R = 1$ 이면 ()가 최적이며, 균형 잡힌 부분 문자열은 문자열 전체 하나다.

$L = 3$ , $R = 2$ 이면 ()()(와 (()() 둘 다 최댓값 3을 준다. 예를 들어 ()()(에서는 1번부터 2번까지의 (), 3번부터 4번까지의 (), 1번부터 4번까지의 ()()가 균형 잡힌 부분 문자열이다.

예제1

예제 1

입력

예상 출력

Case #1: 0
Case #2: 1
Case #3: 3