만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

쌍의 합

면접 대비

시간 제한1초메모리 제한128 MB

요약
정렬된 서로 다른 수 배열에서 합이 M인 쌍 개수를 테스트 케이스마다 셉니다.
난이도

쉬움10점 중 3점

유형
투 포인터, 배열
정답자
아직 제출이 없습니다

문제

크기가 NN인 정수 배열과 정수 MM이 주어진다. 이 배열에서 만들 수 있는 서로 다른 쌍은 N×(N−1)/2N \times (N - 1) / 2개다. 그중 두 원소의 합이 정확히 MM인 쌍이 몇 개인지 구하시오.

예를 들어 배열이 {1,2,3,4}\{1, 2, 3, 4\}이고 M=5M = 5이면, 합이 MM인 쌍은 {1,4}\{1, 4\}와 {2,3}\{2, 3\} 두 개다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. TT는 양의 정수이고 100 000100\,000 이하다.

각 테스트 케이스는 두 줄이다. 첫째 줄에 정수 NN과 MM이 공백 하나로 구분되어 주어진다. NN은 22 이상 20 00020\,000 이하다. 둘째 줄에 배열의 원소 NN개가 공백 하나로 구분되어 주어진다. 배열의 값은 모두 11 이상 1 000 000 0001\,000\,000\,000 이하이고, 서로 다르며 증가하는 순서로 정렬되어 있다.

출력

각 테스트 케이스마다 Case #x: R 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, RR은 두 원소의 합이 정확히 MM인 쌍의 개수다.

예제1

  1. 예제 1

    입력
    5
    8 100
    19 25 32 48 52 68 75 81
    8 100
    19 28 31 49 51 61 72 81
    8 100
    16 22 38 46 58 62 73 81
    8 100
    13 21 32 48 52 67 78 87
    8 100
    13 24 34 43 57 61 76 81
    
    예상 출력
    Case #1: 4
    Case #2: 3
    Case #3: 1
    Case #4: 2
    Case #5: 2