시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 149 59 44 37.288%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

4
32
51
123
282

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhZDUwXHVjMjE4XHViMmQ4IFx1YmFiMFx1Yjc5OCBcdWFkNTBcdWMyZTRcdWM3NDQgXHViMDk4XHVhYzA0IFx1YzBjMVx1YWRmY1x1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNCBcdWMyMThcdWM1YzUgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YWQ1MFx1YzIxOFx1YjJkOCBcdWJhYjBcdWI3OTggXHVhZDUwXHVjMmU0XHVjNzQ0IFx1YjA5OFx1YWMxNFx1YjJlNC4gXHVhY2IwXHVhZDZkIFx1YWQ1MFx1YzIxOFx1YjJkOFx1YzVkMFx1YWM4YyBcdWJkODhcdWI4MjRcdWFjMDBcdWFjOGMgXHViNDE4XHVjNWM4XHVhY2UwLCBcdWFkNTBcdWMyMThcdWIyZDhcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjMjE4IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWQzMTRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYzFiXHVhY2UwIFx1ZDMxNFx1Yzc3NCBcdWJiMzRcdWM1YzdcdWM3NzhcdWM5YzAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LiBcdWIzNzBcdWM3NzRcdWQxMzBcdWJjYTBcdWM3NzRcdWMyYTQgXHVjODcwXHVhZDUwIFx1YjNkOVx1YWRkY1x1YjI5NCBcdWI0NTAgXHVjMjE4XHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWM3OTBcdWI5YWMoXHVjNzU4IFx1YzIyYlx1Yzc5MClcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWFjYjlcdWNlNThcdWIyOTQgXHVjMzBkXHVjNzQ0IFx1ZDMxNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTg4XHViMmU0LiAoXHVhY2I5XHVjZTU4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyZWNcdWI3N2NcdWIzYzQgXHViNDFjXHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjMjE5XHVjODFjXHViOTdjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBbMSwgMTA8c3VwPjE4PFwvc3VwPl0gXHViYzk0XHVjNzA0IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWFjMDAgXHVhZDUwXHVjMjE4XHViMmQ4XHVjNzc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWMyMTlcdWM4MWNcdWI4NWMgXHVjODA0XHViMmVjXHVkNTVjIFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YzIxOFx1YWMwMCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMzE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktPTVBJXHUwMTA2SSIsImRlc2NyaXB0aW9uIjoiPHA+QWZ0ZXIgc3VjY2Vzc2Z1bGx5IHNvbHZpbmcgaGlzIG1hdGggaG9tZXdvcmsgZnJvbSB0aGUgcHJldmlvdXMgdGFzaywgTWlya28gaGFzIGJlY29tZSBib3JlZCwgc28gaGUgaGFzIG1hZGUgYSBsaXN0IG9mIE4gbGFyZ2UgaW50ZWdlcnMuIE9uIHRoZSBsaXN0IHRoZXJlIGFyZSBzb21lIHBhaXJzIG9mIG51bWJlcnMgdGhhdCBoZSBsaWtlcywgYW5kIHNvbWUgcGFpcnMgaGUgZG9lc24mcnNxdW87dCBsaWtlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBoYXMgbmFtZWQgdGhlIHBhaXJzIHRoYXQgaGUgbGlrZXMgcGFscy4gVHdvIG51bWJlcnMgYXJlIHBhbHMgaWYgdGhleSBoYXZlIGF0IGxlYXN0IG9uZSBkaWdpdCBpbiBjb21tb24gKG5vdCBuZWNlc3NhcmlseSBpbiB0aGUgc2FtZSBwb3NpdGlvbikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gY291bnQgaG93IG1hbnkgcGFpcnMgb2YgbnVtYmVycyBpbiBoaXMgbGlzdCBhcmUgcGFscy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBmcm9tIHRoZSByYW5nZSBbMSwgMTAxOF0sIGEgbnVtYmVyIGZyb20gTWlya28mcnNxdW87cyBsaXN0LiBObyB0d28gbnVtYmVycyBpbiB0aGUgbGlzdCB3aWxsIGJlIGVxdWFsLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG51bWJlciBvZiBwYWlycyB0aGF0IGFyZSBwYWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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