시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 17 16 51.613%

문제

상근이는 전 세계에 존재하는 모든 크로스워드 퍼즐을 풀었다. 더 이상 풀 퍼즐이 없기 때문에, 새로운 퍼즐을 만드려고 한다.

단어의 길이가 같은 네 단어를 이용해서 정사각형 모양의 크로스워드 퍼즐을 만들 수 있다. 가로로 놓인 단어는 왼쪽부터 오른쪽으로 읽고, 세로로 놓은 단어는 위에서 아래로 읽는다. 아래 그림은 "HLAD", "NIVA", "HSIN", "DEDA"를 이용해서 만든 크로스워드 퍼즐의 한 예이다.

길이가 모두 같은 단어가 여러개 주어졌을 때, 서로 다른 정사각형 모양의 크로스워드 퍼즐을 몇 개나 만들 수 있는지 구하는 프로그램을 작성하시오. 한 단어는 꼭 한 번만 사용해야 한다. 두 정사각형이 적어도 한 위치에서 문자가 다르다면, 두 크로스워드퍼즐은 다른 퍼즐이다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (4 ≤ N ≤ 100,000) 다음 N개 줄에는 알파벳 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 모두 같으며, 10글자 이내이다. 입력 되는 모든 단어들은 서로 다르다.

출력

첫째 줄에 입력으로 주어진 단어를 이용해서 서로 다른 크로스워드 퍼즐을 몇 개나 만들 수 있는지 출력한다.

예제 입력 1

4
NIVA
HLAD
HSIN
DEDA

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODA0IFx1YzEzOFx1YWNjNFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwXHVjNWM4XHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1ZDQ4MCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWIxMjQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIxOTNcdWM3NzggXHViMmU4XHVjNWI0XHViMjk0IFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzdkXHVhY2UwLCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViMTkzXHVjNzQwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4XHViODVjIFx1Yzc3ZFx1YjI5NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCAmcXVvdDtITEFEJnF1b3Q7LCAmcXVvdDtOSVZBJnF1b3Q7LCAmcXVvdDtIU0lOJnF1b3Q7LCAmcXVvdDtERURBJnF1b3Q7XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTAgXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWQ1NWMgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Nyb3Nzd29yZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjVweDsgd2lkdGg6MTU4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzc0XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzVlY1x1YjdlY1x1YWMxYyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWJhODcgXHVhYzFjXHViMDk4IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWQ1NWMgXHViMmU4XHVjNWI0XHViMjk0IFx1YWYyZCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YmE3NCwgXHViNDUwIFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkY1x1ZDM3Y1x1Yzk5MFx1Yzc0MCBcdWIyZTRcdWI5NzggXHVkMzdjXHVjOTkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoNCAmbGU7IE4gJmxlOyAxMDAsMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzNjXHViYTcwLCAxMFx1YWUwMFx1Yzc5MCBcdWM3NzRcdWIwYjRcdWM3NzRcdWIyZTQuJm5ic3A7XHVjNzg1XHViODI1IFx1YjQxOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YmE4NyBcdWFjMWNcdWIwOTggXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSQVpCSUJSSUdBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgYWxyZWFkeSBzb2x2ZWQgYWxsIGNyb3Nzd29yZHMgYXZhaWxhYmxlIGluIGRhaWx5IG5ld3NwYXBlcnMsIGFuZCBoZSBpcyB0b28gaW50aW1pZGF0ZWQgYnkgQUNUQSB0byBkb3dubG9hZCBuZXcgb25lcyBmcm9tIHRoZSBJbnRlcm5ldC4gTm93IGhlIGhhcyBhc2tlZCBGcmFuZSB0byBjaGFsbGVuZ2UgaGltIHdpdGggYSBwcm9ncmFtbWluZyBwcm9ibGVtLiBGcmFuZSBoYXMgZWFnZXJseSByZXNwb25kZWQgd2l0aCBhIGJyYW5kIG5ldyB0YXNrLCBhbmQgd2FzIGtpbmQgZW5vdWdoIG5vdCB0byBsb2NrIHRoZSB0YXNrIHVuZGVyIGNvcHlyaWdodCBwcm90ZWN0aW9uLCBzbyB5b3UgYXJlIGFsbG93ZWQgdG8gYXR0ZW1wdCBpdCB0b28hPFwvcD5cclxuXHJcbjxwPkZvdXIgd29yZHMgd2l0aCBlcXVhbCBsZW5ndGhzIGNhbiBiZSBwdXQgdG9nZXRoZXIgaW4gYSBzcXVhcmUgc3VjaCB0aGF0IHR3byB3b3JkcyBtYXJrIGhvcml6b250YWwgZWRnZXMsIHdoaWxlIHRoZSBvdGhlciB0d28gbWFyayB2ZXJ0aWNhbCBlZGdlcy4gSG9yaXpvbnRhbCB3b3JkcyBhcmUgcmVhZCBsZWZ0IHRvIHJpZ2h0LCBhbmQgdmVydGljYWwgb25lcyBmcm9tIHRvcCB0byBib3R0b20uIENvcm5lciBsZXR0ZXJzIGFyZSBzaGFyZWQgYnkgdGhlIHR3byBuZWlnaGJvdXJpbmcgZWRnZXMuIFRoZSBmaWd1cmUgYmVsb3cgc2hvd3Mgb25lIHBvc3NpYmxlIHNxdWFyZSBjcmVhdGVkIGZyb20gd29yZHMgJmxkcXVvO0hMQUQmcmRxdW87LCAmbGRxdW87TklWQSZyZHF1bzssICZsZHF1bztIU0lOJnJkcXVvOywgJmxkcXVvO0RFREEmcmRxdW87PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY3Jvc3N3b3JkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyNXB4OyB3aWR0aDoxNThweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMsIGdpdmVuIGEgbGlzdCBvZiBlcXVhbC1sZW5ndGggd29yZHMsIHRvIGNvbXB1dGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgc3F1YXJlcyB0aGF0IGNhbiBiZSBwdXQgdG9nZXRoZXIgZnJvbSBhIHN1YnNldCBvZiB0aGVzZSB3b3Jkcy4gWW91IGFyZSBub3QgYWxsb3dlZCB0byByZXBlYXQgYSB3b3JkIGluIHRoZSBzYW1lIHNxdWFyZS4gVHdvIHNxdWFyZXMgYXJlIGRpZmZlcmVudCBpZiB0aGV5IGRpZmZlciBpbiBhdCBsZWFzdCBvbmUgY2hhcmFjdGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoNCAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiB3b3JkcyBpbiB0aGUgbGlzdC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHdvcmQgY29uc2lzdGluZyBvbmx5IG9mIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlcnMuPFwvcD5cclxuXHJcbjxwPkVhY2ggd29yZCB3aWxsIGNvbnRhaW4gYXQgbW9zdCAxMCBjaGFyYWN0ZXJzLiBBbGwgd29yZHMgd2lsbCBiZSBkaXN0aW5jdCBhbmQgaGF2ZSBlcXVhbCBsZW5ndGguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIGRpc3RpbmN0IHNxdWFyZXMuPFwvcD5cclxuXHJcbjxwPk5vdGU6IFRlc3QgZGF0YSB3aWxsIGVuc3VyZSB0aGF0IHRoZSBzb2x1dGlvbiBmaXRzIGluIGEgNjQtYml0IGludGVnZXIgZGF0YSB0eXBlIChpbnQ2NCBpbiBQYXNjYWwsIGxvbmcgbG9uZyBpbiBDXC9DKyspLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: hihihi