시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.8 초 256 MB 2 2 (100%) 1
문제
Martin은 대기업의 전산 관리자로 막 취직하였다. 회사는 1980년대 이래로 한 번도 인증시스템을 바꾼 적이 없었다. 각 직원은 PIN(personal identification number)로 불리는 4자리의 식별부호를 가지고 있다. 아무도 사용자명이나 비밀번호를 사용하지 않고 PIN을 입력하는 것만으로 시스템에 접속할 수 있다. 회사가 거대해지며 그들은 PIN에 문자를 사용할 수도 있게 했지만 길이는 그대로 놔뒀다. Martin은 이런 상황에 불만을 품고 있었다. 서로 PIN이 한 자리만 다른 사람들이 있다고 가정해보자, 예를 들어 PIN이 61ab와 62ab일 수 있다. 만약 앞의 사람이 실수로 1 대신 2를 누르게 돼도 여전히 시스템에 접속할 수 있다. Martin은 현재 사용 중인 PIN에 대한 통계를 내보고 싶었고 특히 1개, 2개, 3개, 4개의 자리수가 다른 PIN의 쌍들이 각각 몇 개인지 알아내고 싶어한다. 그는 이 숫자들이 상사로 하여금 더 나은 시스템에 투자하도록 할만큼 의미가 있기를 기대한다. PIN들의 리스트와 정수 $D$가 주어졌을 때 정확하게 $D$자리만큼 다른 PIN 쌍의 개수를 구하여라.
입력
첫째 줄에 띄어쓰기로 구분된 두 개의 정수 $N, D$가 주어진다. $N$은 PIN의 개수이고 $D$는 확인하고자 하는 만큼의 자릿수 차이이다. 다음 $N$개의 줄에는 각각 하나의 PIN이 주어진다.
출력
정확하게 $D$개의 자리가 다른 PIN 쌍의 개수를 출력한다.
힌트
#### 제약조건 모든 테스트 케이스에서 $2 \le N \le 50,000$ 이고 $1 \le D \le 4$ 이다. PIN은 길이가 4이며 숫자 혹은 a-z 사이의 알파벳 소문자로 이루어져 있다. 입력으로 주어진 PIN들은 서로 다르다고 가정해도 좋다.
$15$점에 해당하는 서브태스크에서 $N \le 2,000$ 이다.
$60$점에 해당하는 서브태스크에서 $D \le 2$ 이며 나머지 중 $30$점은 $D = 1$ 이다.
$75$점에 해당하는 서브태스크에서 모든 PIN은 숫자 혹은 a-f 사이의 알파벳 소문자로 이루어져 있다. 즉 16진수로 볼 수 있는 것이다. 시간 제한은 $0.8$초, 메모리 제한은 $256MB$이다. #### 입력 예제 1 ``` 4 1 0000 a010 0202 a0e2 ``` #### 출력 예제 1 ``` 0 ``` 이 PIN들은 각각 적어도 한 개 이상의 자리에서 값이 다르다. #### 입력 예제 2 ``` 4 2 0000 a010 0202 a0e2 ``` #### 출력 예제 2 ``` 3 ``` 3개의 쌍에서 정확하게 2자리씩 값이 다르다: (0000,a010), (0000,0202) 그리고 (a010,a0e2).