연습문제

CPTI

난이도
Lv. 3
제출
369 명
참가자
89 명
정답률
23.14 %
지원 언어
C
C++
Java
Python
Rust
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 2초 1024MB
C++ 2초 1024MB
Java 3초 1024MB
Python 3초 1024MB
Rust 2초 1024MB

코드런 나라에는 총 명의 사람이 살고 있습니다. 이 나라에는 사람들의 성격을 나타내는 CPTI(CodeRun Person Type Indicator)라는 지표가 존재합니다.

CPTI는 길이 의 이진 문자열로 표현되며, 각 자리의 값은 해당 성격 영역에 대해 그 사람이 긍정형()인지 부정형()인지를 나타냅니다. 예를 들어, 성격 영역이 세 개인 경우, 첫 번째와 세 번째 지표가 긍정형이고 두 번째 지표가 부정형이라면, 101으로 표현됩니다.

두 사람의 CPTI를 비교했을 때, 최대 두 가지 영역에서만 성격이 다르면 두 사람은 친밀감을 느낀다고 합니다. 예를 들어, 인 경우, CPTI가 각각 000, 101인 사람들은 성격이 다른 영역이 개이므로 친밀감을 느낍니다. 그렇지만, CPTI가 각각 010, 101인 사람들은 세 개의 영역 모두에서 성격이 모두 다르므로, 친밀감을 느끼지 않습니다.

코드런 나라의 왕인 James는 이 나라에 살고 있는 사람들 중에서 서로 친밀감을 느끼는 사람 쌍이 얼마나 되는지 알고 싶어합니다.

James를 위해 서로 친밀감을 느끼는 사람 쌍의 수를 계산하는 프로그램을 작성하세요. 사람 쌍의 경우 순서를 고려하지 않습니다.

제약조건

[문제 제약 조건]

[조건 1]

[조건 2]


[서브 태스크별 제약 조건]

Subtask1 (12점): ,

Subtask2 (18점):

Subtask3 (70점): 문제 조건 외에 별도의 제한이 없습니다.

입력형식

첫 번째 줄에 사람의 수 과 CPTI를 나타내는 문자열의 길이 이 주어집니다.

두 번째 줄부터 다음 개의 줄 중 번째 줄에는 번 사람의 성격을 나타내는 문자열이 주어집니다. 각 문자열은 길이 이며 01로만 이루어져 있습니다.

출력형식

친밀감을 느끼는 사람 쌍의 수를 첫 번째 줄에 출력합니다.

입력예제1

3 3 001 010 100

출력예제1

3

모든 사람의 쌍이 서로 친밀감을 느낍니다.

입력예제2

3 3 000 010 101

출력예제2

2

두 번째와 세 번째 사람의 경우에는 서로 친밀감을 느낄 수 없지만, 나머지 사람 쌍들은 모두 친밀감을 느낍니다.