21396번 - 이진수 더하기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) (하단 참고) | 512 MB | 371 | 100 | 75 | 30.120% |
문제
Albert는 최근 2진수에 대해 배워 열심히 2진수 덧셈을 연습하고 있다. 하지만 아직 익숙치 않아서 "받아 올림"을 깜빡하곤 한다.
예를 들어 3 + 5의 경우 2진수로 표현하면 11(2) + 101(2) = 1000(2) (10진수 8) 이 되어야 한다.
하지만 2진수로 표현한 두 수를 더할 때 받아 올림을 하지 않으면 11(2) + 101(2) = 110(2) (10진수 6)이 된다. 구체적으로, 20에 해당하는 가장 아래 자리를 더하면 1+1 = 0 이 되고 (올림이 발생하지만 Albert는 이를 무시한다), 21에 해당하는 자리의 수를 더하면 1+0 = 1, 마지막으로 22에 해당하는 자리의 수를 더하면 0+1 = 1이 되어 결과적으로 110(2) = 6을 얻는다.
Albert는 받아 올림이 없는 2진수 덧셈이 재밌다고 생각되어 아래와 같은 문제를 풀어보기로 했다.
n개의 정수 v[1], v[2],..., v[n]가 주어졌을 때 S(i, j)는 받아 올림 없이 2진수 덧셈으로 v[i] + v[j]를 계산한 값이라고 하자.
Albert는 임의의 정수 x에 대해 1 ≤ i < j ≤ n 과 S(i, j) = x 를 만족하는 쌍 (i, j)의 개수를 세고 싶다.
예를 들어 n = 4, v = [3 7 5 6] 그리고 x = 4 라 하자.
- S(1, 2) = 3 + 7 = 4
- S(1, 3) = 3 + 5 = 6
- S(1, 4) = 3 + 6 = 5
- S(2, 3) = 7 + 5 = 2
- S(2, 4) = 7 + 6 = 1
- S(3, 4) = 5 + 6 = 3
이 경우 조건을 만족하는 쌍은 (i, j) = (1, 2)가 유일하다.
입력으로 n, x, 그리고 n개의 정수 v[1], ..., v[n]이 주어졌을 때, Albert를 도와 조건을 만족하는 쌍의 개수를 세어보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어지는데 첫 줄에 n과 x가 공백으로 구분 되어 주어진다.
둘째 줄에는 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 조건을 만족하는 쌍의 개수를 한 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 100,000
- 0 ≤ x ≤ 2,000,000,000
- 0 ≤ v[i] ≤ 2,000,000,000 (1 ≤ i ≤ n)
예제 입력 1
3 4 0 2 2 3 3 4 1 2 3 3 2 4 4 3 7 5 6
예제 출력 1
2 4 1
예제 1: (1, 2) 와 (3, 4) 두 쌍이 조건을 만족한다.
예제 2: (1, 2), (1, 3), (2, 4), (3, 4) 총 네 쌍이 조건을 만족한다.
예제 3: 본문에서 다루었다.
시간 제한
- Java 8: 2 초
- Java 8 (OpenJDK): 2 초
- Java 11: 2 초
- Kotlin (JVM): 2 초
- Java 15: 2 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호