시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 488 111 91 30.435%

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

  • 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
  • ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
  • 상근: 근데?
  • ??: 내 말 아직 안끝났어. 말콤이 어느날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
  • 상근: 아? 근데 K는 어떻게 구해?
  • ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
  • 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

출력

첫째 줄에 좋은 친구가 몇 쌍이 있는지 출력한다.

예제 입력 1

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMwNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNjU4XHVhYzExXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YjM1OCBcdWIwOThcdWM3NzRcdWM1ZDAgXHVjMjE4XHViMmE1IFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWIyZTRcdWMyZGNcdWJjZjRcdWFjZTAgXHVhZDUwXHViMzAwXHVjNWQwIFx1Yzc4NVx1ZDU1OVx1ZDU4OFx1YWNlMCwgXHVjZDA4XHViNGYxXHVkNTU5XHVhZDUwIFx1YzEyMFx1YzBkZFx1YjJkOFx1YzczY1x1Yjg1YyBcdWNkZThcdWM5YzFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiBcdWM2OTRcdWM5OTggXHVjNTYwXHViNGU0XHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1Yjk3YyBcdWMwYWNcdWFkYzBcdWM5YzAgXHVjNTRhXHViMDk4XHViZDEwLiBcdWIwYjRcdWFjMDAgXHVjNTVlXHVjNWQwXHVjMTFjIFx1YmNmNFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzQsIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmNjNFx1Yjg1YyBcdWM1YzZcdWIyOTQgXHVhYzgzIFx1YWMxOVx1YzU0NC48XC9saT5cclxuXHQ8bGk+Pz86IFx1YzYyNFx1YmU2MCEgXHVjNjI0XHViZTYwXHViMjk0IFx1YjlkMFx1Y2Y2NFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWM2NDAgXHVjMTMxXHVjODAxXHVjNzc0XHViNzdjXHViMjk0IFx1Y2M0NSBcdWM1NDggXHVjNzdkXHVjNWI0IFx1YmQyNFx1YzViND8gXHVjNzc0IFx1Y2M0NVx1YzVkMFx1YjI5NCBcdWMxMzFcdWM4MDFcdWFjZmMgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YmIzNFx1YzJhOCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNzg4XHViMjk0XHVjOWMwIFx1YjA5OFx1YzY0MC4gXHVjNjk0XHVjOTk4IFx1YzU2MFx1YjRlNFx1Yzc0MCBcdWNlNWNcdWFkNmNcdWI5N2MgXHVjMGFjXHVhZGMwXHVhZTMwIFx1YzgwNFx1YzVkMCBcdWJhM2NcdWM4MDAgXHVhZGY4IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWJjMTggXHViNGYxXHVjMjE4XHViOTdjIFx1YzBiNFx1ZDNiNFx1YmQxMC4gXHViOWQwXHVjZjY0XHVjNzQwIFx1Yzc3NCBcdWM1ZjBcdWFkNmNcdWI5N2MgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyA2XHViMTQ0XHViM2Q5XHVjNTQ4IFx1Y2QwOFx1YjRmMVx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3M2NcdWI4NWMgXHVjNzA0XHVjN2E1IFx1ZDU4OFx1YzVjOFx1YzljMC4gXHVkNTU4XHVjOWMwXHViOWNjLCA2XHViMTQ0XHVjNzc0XHViNzdjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHViY2Y0XHViMGM4XHVjOWMwXHViOWNjLCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzQwIFx1YWNiMFx1YWQ2ZCBcdWFjYjBcdWI4NjBcdWM3NDQgXHVjNWJiXHVjOWMwIFx1YmFiYlx1ZDU4OFx1YzViNC48XC9saT5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiBcdWFkZmNcdWIzNzA/PFwvbGk+XHJcblx0PGxpPj8/OiBcdWIwYjQgXHViOWQwIFx1YzU0NFx1YzljMSBcdWM1NDhcdWIwNWRcdWIwYWNcdWM1YjQuIFx1YjlkMFx1Y2Y2NFx1Yzc3NCBcdWM1YjRcdWIyOTBcdWIwYTAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1Y2QwOFx1YjRmMVx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI0MThcdWM1YjQgXHVkNTU5XHVhZDUwXHViOTdjIFx1ZDY1Y1x1YmNmNFx1ZDU1OFx1YjI5NCBcdWFmYzhcdWM3NDQgXHVhZmI4XHVjNWM4XHVjNWI0LiBcdWFkZmNcdWIzNzAgXHVjN2EwXHVjNzQ0IFx1YWU2OFx1YWNlMCBcdWIwOThcdWIyYzggXHViMGI0XHVhYzAwIFx1YWZjOFx1Yzc0NCBcdWFmYjhcdWFjZTAgXHVjZDA4XHViNGYxXHVkNTU5XHVjMGRkXHVjNzc0IFx1YjQxY1x1YWM3NFx1YzljMCwgXHVjNTQ0XHViMmM4XHViYTc0IFx1Y2QwOFx1YjRmMVx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWFmYzhcdWM3NDQgXHVhZmI4XHVhY2UwIFx1YzljMFx1YWUwOFx1Yzc1OCBcdWIwYjRcdWFjMDAgXHViNDE4XHVjNWI0XHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YmFhOFx1Yjk3NFx1YWNhMFx1YjI5NFx1YWM3MFx1YzU3Yy4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YjlkMFx1Y2Y2NFx1Yzc0MCBcdWMwYzFcdWMyZGRcdWM4MDFcdWM3NzggXHVjMGFjXHVhY2UwIFx1YmMyOVx1YzJkZFx1YzVkMCBcdWQwNzAgXHVjNzU4XHViYjM4XHVjNzQ0IFx1YWMwMFx1Yzg0Y1x1YzljMC4gXHVhZGY4IFx1YjU0YyBcdWI5ZDBcdWNmNjRcdWM3NDAgXHVhZTY4XHViMmVjXHVjNTU4XHViMzU4XHVhYzcwXHVjNTdjLiBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTAgXHVjZTVjXHVhZDZjXHViMjk0IFx1YmQ4MFx1YzljOFx1YzVjNlx1YWQ2Y1x1YjA5OC4gXHVhZGY4XHVjODFjXHVjMTFjXHVjNTdjIFx1YzU0Y1x1YWM4Y1x1YjQxY1x1YWM3MFx1YzU3Yy4gXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWFjZmMgXHViYzE4IFx1YjRmMVx1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgS1x1Yjk3YyBcdWIxMThcdWM3M2NcdWJhNzQgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YjI5NFx1YWM3MC48XC9saT5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiBcdWM1NDQ/IFx1YWRmY1x1YjM3MCBLXHViMjk0IFx1YzViNFx1YjViYlx1YWM4YyBcdWFkNmNcdWQ1NzQ/PFwvbGk+XHJcblx0PGxpPj8/OiBLXHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAuIFx1YWRmY1x1YjM3MCwgXHViMzU0IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWMwYWNcdWMyZTRcdWM3NzQgXHVjNzg4XHVjNWI0LiBcdWNlNWNcdWFkNmNcdWM2NDAgXHVjODhiXHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWM1N2MuIFx1YjlkMFx1Y2Y2NFx1Yzc3NCBcdWNlNWNcdWFkNmNcdWM2NDAgXHVjMTMxXHVjODAxXHVjNzQ0IFx1YzRmMFx1YWNlMCAyXHViMTQ0IFx1YjRhNFx1YzVkMCBcdWIwYjggXHVjYzQ1XHVjNzc4IFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWI3N2NcdWIyOTQgXHVjYzQ1XHVjNWQwXHViMjk0IFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWIyOTQgXHVjNzc0XHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM1NDRcdWM1N2MgXHViNDFjXHViMmU0XHViMjk0IFx1YjlkMFx1Yzc3NCBcdWIwOThcdWM2NDAuPFwvbGk+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogXHVjNTQ0ISBcdWFkZjhcdWI3ZmMgXHViMDljIFx1YzYyNFx1YjI5OCBcdWM5ZDFcdWM1ZDAgXHVhYzAwXHVjMTFjIFx1YzZiMFx1YjlhYyBcdWJjMThcdWM1ZDAgXHVjODhiXHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWJhODcgXHVjMzBkXHVjNzc0XHViMDk4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NzRcdWJkMTBcdWM1N2MgXHVhY2EwXHVjNWI0ITxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWJjMThcdWM3NTggTlx1YmE4NSBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzEzMVx1YzgwMVx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjXHVhYzAwIFx1YmE4NyBcdWMzMGRcdWM3NzRcdWIwOTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjXHViMjk0IFx1YjRmMVx1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgS1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTc0XHVjMTFjIFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgMzAwLDAwMCwgMSAmbGU7IEsgJmxlOyBOKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YmMxOCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzEzMVx1YzgwMVx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIDJcdWFlMDBcdWM3OTAgfiAyMFx1YWUwMFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BTENPTE0iLCJkZXNjcmlwdGlvbiI6IjxwPlNpbmNlIHRlYWNoZXIgSGVya2FiZSBoYXMgc3RhcnRlZCByYW5raW5nIGhpcyBOIHN0dWRlbnRzLCB0aGUgbnVtYmVyIG9mIGZyaWVuZHNoaXBzIGluIGhpcyBjbGFzcyBoYXMgc2hhcnBseSBmYWxsZW4uIFRoZSBzdHVkZW50cyBuZWFyIHRoZSBib3R0b20gb2YgdGhlIHJhbmtpbmdzIGxpc3QgaGF2ZSBiZWNvbWUgamVhbG91cyBvZiB0aGUgdG9wIHN0dWRlbnRzLCB3aGlsZSB0aGUgdG9wIHN0dWRlbnRzIHN0YXJ0ZWQgbG9va2luZyBkb3duIG9uIHRoZWlyIGxlc3Mgc3VjY2Vzc2Z1bCBjb2xsZWFndWVzLjxcL3A+XHJcblxyXG48cD5BY2NvcmRpbmcgdG8gTWFsY29sbSYjMzk7cyBvYnNlcnZhdGlvbnMsIHRoZSBmb2xsb3dpbmcgcnVsZSBob2xkczogdHdvIHN0dWRlbnRzIGFyZSBmcmllbmRzIGlmIHRoZWlyIHJhbmtzIGFyZSBjbG9zZSBlbm91Z2gsIG1vcmUgcHJlY2lzZWx5LCBpZiB0aGV5IGRpZmZlciBieSBhdCBtb3N0IEsuIEZvciBleGFtcGxlLCBpZiBLID0gMSwgdGhlbiBvbmx5IG5laWdoYm91cmluZyBzdHVkZW50cyBvbiB0aGUgcmFua2luZ3MgbGlzdCBhcmUgZnJpZW5kcy4gRnVydGhlcm1vcmUsIHR3byBzdHVkZW50cyBhcmUgZ29vZCBmcmllbmRzIGlmIHRoZXkgYXJlIGZyaWVuZHMgYW5kIHRoZWlyIG5hbWVzIGhhdmUgdGhlIHNhbWUgbGVuZ3RoLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgcGFpcnMgb2YgZ29vZCBmcmllbmRzIGluIHRoaXMgZ2lmdGVkIGNsYXNzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgzICZsZTsgTiAmbGU7IDMwMCAwMDApIGFuZCBLICgxICZsZTsgSyAmbGU7IE4pLCBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgc3R1ZGVudCYjMzk7cyBuYW1lLiBUaGUgbmFtZXMgYXJlIGdpdmVuIGluIHRoZSBvcmRlciB0aGV5IGFwcGVhciBvbiB0aGUgcmFua2luZ3MgbGlzdC4gVGhleSBjb25zaXN0IG9mIGJldHdlZW4gMiBhbmQgMjAgKGluY2x1c2l2ZSkgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgb2YgcGFpcnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #3 3번