nnaxh0   11달 전

문제

색상은 빨강(red), 초록(green), 파랑(blue)의 세 가지 성분 값으로 이루어진 순서쌍(트리플)로 표현할 수 있으며, 각 성분 값은 0 이상 K 이하(포함)이다.
예를 들어 K = 3인 색상 시스템에서는 (0, 2, 3)과 (0, 3, 2)는 서로 다른 두 가지 가능한 색상이다.

우리는 어떤 색상이 bland하다고 부르기를, 그 색상의 모든 성분 쌍 간의 차이가 V를 넘지 않을 때이자 그때에 한해서라고 정의한다.
예를 들어 K = 2이고 V = 1인 시스템에서 색상 (2, 1, 1)은 bland이다.
그 이유는 빨강과 초록의 차이가 1, 빨강과 파랑의 차이가 1, 초록과 파랑의 차이가 0이며, 이들 중 어느 것도 1을 초과하지 않기 때문이다.
하지만 (2, 1, 0)은 bland가 아니다. 빨강과 파랑 성분의 차이가 1을 초과하기 때문이다.

터너 씨는 우울한 풍경 이미지를 만드는 것을 좋아하며, bland 색상이 많이 존재하는 색상 시스템을 설계하고 싶어 한다.
K와 V가 주어졌을 때, 서로 다른 bland 색상의 개수가 몇 개인지 구하여라.

보통 Google Code Jam 문제는 Small 입력 1개와 Large 입력 1개로 구성되어 있다.
하지만 이 문제는 Small 입력 1개와 Large 입력 2개로 구성되어 있다.

Small 입력을 해결하면 두 개의 Large 입력 중 하나를 다운로드할 수 있다.
Small 입력은 시간 페널티를 감수하고 재도전할 수 있지만, 각 Large 입력에 대해서는 한 번의 기회만 주어진다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.
이후 T개의 줄에 걸쳐, 각 줄마다 두 개의 정수 K와 V가 공백으로 구분되어 주어진다.

제한 조건

  • 1 ≤ T ≤ 100

  • V ≤ K

  • 0 ≤ K ≤ 2555

  • 0 ≤ V ≤ 555

  • 모든 정답은 32비트 부호 있는 정수 범위에 들어간다.

출력

각 테스트 케이스마다 한 줄씩 다음 형식으로 출력한다.

Case #x: y

여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 서로 다른 bland 색상의 개수이다.

댓글을 작성하려면 로그인해야 합니다.