시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 153 61 46 38.017%

문제

상근이는 데이터베이스 수업 시간에 교수님 몰래 교실을 나갔다. 결국 교수님에게 불려가게 되었고, 교수님은 다음과 같은 수학 숙제를 내주었다.

정수 N개가 주어진다. 이 때, 친구의 개수를 구하라.

상근이는 이 문제를 받고 친구가 무엇인지 궁금해졌다. 데이터베이스 조교 동규는 두 수를 이루는 숫자가 적어도 하나 겹치는 쌍을 친구라고 한다고 했다. (겹치는 위치는 달라도 된다)

상근이의 숙제를 하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

다음 N개 줄에는 [1, 1018] 범위 안에 있는 양의 정수가 주어진다. 이 수가 교수님이 상근이에게 숙제로 전달한 수이다. 같은 수가 두 번 이상 주어지지 않는다.

출력

첫째 줄에 친구의 개수를 출력한다.

예제 입력 1

4
32
51
123
282

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhZDUwXHVjMjE4XHViMmQ4IFx1YmFiMFx1Yjc5OCBcdWFkNTBcdWMyZTRcdWM3NDQgXHViMDk4XHVhYzA0IFx1YzBjMVx1YWRmY1x1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNCBcdWMyMThcdWM1YzUgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YWQ1MFx1YzIxOFx1YjJkOCBcdWJhYjBcdWI3OTggXHVhZDUwXHVjMmU0XHVjNzQ0IFx1YjA5OFx1YWMxNFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YWQ1MFx1YzIxOFx1YjJkOFx1YzVkMFx1YWM4YyBcdWJkODhcdWI4MjRcdWFjMDBcdWFjOGMgXHViNDE4XHVjNWM4XHVhY2UwLCBcdWFkNTBcdWMyMThcdWIyZDhcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMjE4IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWNlNWNcdWFkNmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYzFiXHVhY2UwIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCZuYnNwO1x1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNCBcdWM4NzBcdWFkNTAgXHViM2Q5XHVhZGRjXHViMjk0IFx1YjQ1MCBcdWMyMThcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4IFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWMzMGRcdWM3NDQgXHVjZTVjXHVhZDZjXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1ODhcdWIyZTQuIChcdWFjYjlcdWNlNThcdWIyOTQgXHVjNzA0XHVjZTU4XHViMjk0IFx1YjJlY1x1Yjc3Y1x1YjNjNCBcdWI0MWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWMyMTlcdWM4MWNcdWI5N2MgXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFsxLCAxMDxzdXA+MTg8XC9zdXA+XSBcdWJjOTRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YWMwMCBcdWFkNTBcdWMyMThcdWIyZDhcdWM3NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzIxOVx1YzgxY1x1Yjg1YyBcdWM4MDRcdWIyZWNcdWQ1NWMgXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjMjE4XHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNlNWNcdWFkNmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09NUElcdTAxMDZJIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciBzdWNjZXNzZnVsbHkgc29sdmluZyBoaXMgbWF0aCBob21ld29yayBmcm9tIHRoZSBwcmV2aW91cyB0YXNrLCBNaXJrbyBoYXMgYmVjb21lIGJvcmVkLCBzbyBoZSBoYXMgbWFkZSBhIGxpc3Qgb2YgTiBsYXJnZSBpbnRlZ2Vycy4gT24gdGhlIGxpc3QgdGhlcmUgYXJlIHNvbWUgcGFpcnMgb2YgbnVtYmVycyB0aGF0IGhlIGxpa2VzLCBhbmQgc29tZSBwYWlycyBoZSBkb2VzbiZyc3F1bzt0IGxpa2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGhhcyBuYW1lZCB0aGUgcGFpcnMgdGhhdCBoZSBsaWtlcyBwYWxzLiBUd28gbnVtYmVycyBhcmUgcGFscyBpZiB0aGV5IGhhdmUgYXQgbGVhc3Qgb25lIGRpZ2l0IGluIGNvbW1vbiAobm90IG5lY2Vzc2FyaWx5IGluIHRoZSBzYW1lIHBvc2l0aW9uKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBjb3VudCBob3cgbWFueSBwYWlycyBvZiBudW1iZXJzIGluIGhpcyBsaXN0IGFyZSBwYWxzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGZyb20gdGhlIHJhbmdlIFsxLCAxMDxzdXA+MTg8XC9zdXA+XSwgYSBudW1iZXIgZnJvbSBNaXJrbyZyc3F1bztzIGxpc3QuIE5vIHR3byBudW1iZXJzIGluIHRoZSBsaXN0IHdpbGwgYmUgZXF1YWwuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBhaXJzIHRoYXQgYXJlIHBhbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 4번