시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB102423447.887%

문제

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

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

H L A D
S     E
I     D
N I V A

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

입력

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

출력

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

예제 입력 1

4
NIVA
HLAD
HSIN
DEDA

예제 출력 1

2

예제 입력 2

6
BAKA
BARA
BALC
CALC
ARHC
BLIC

예제 출력 2

8
W3sicHJvYmxlbV9pZCI6IjI4MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODA0IFx1YzEzOFx1YWNjNFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwXHVjNWM4XHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1ZDQ4MCBcdWQzN2NcdWM5OTBcdWM3NzQgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGM4XHViODVjXHVjNmI0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWIxMjQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMFx1Yjg1Y1x1Yjg1YyBcdWIxOTNcdWM3NzggXHViMmU4XHVjNWI0XHViMjk0IFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzdkXHVhY2UwLCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViMTkzXHVjNzQwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4XHViODVjIFx1Yzc3ZFx1YjI5NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCAmcXVvdDtITEFEJnF1b3Q7LCAmcXVvdDtOSVZBJnF1b3Q7LCAmcXVvdDtIU0lOJnF1b3Q7LCAmcXVvdDtERURBJnF1b3Q7XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTAgXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjIFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWQ1NWMgXHVjNjA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZCB0YWJsZS1jZW50ZXItMjAgdGQtY2VudGVyXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+SDxcL3RkPlxyXG5cdFx0XHQ8dGQ+TDxcL3RkPlxyXG5cdFx0XHQ8dGQ+QTxcL3RkPlxyXG5cdFx0XHQ8dGQ+RDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5TPFwvdGQ+XHJcblx0XHRcdDx0ZD4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkPiZuYnNwOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+RTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5JPFwvdGQ+XHJcblx0XHRcdDx0ZD4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkPiZuYnNwOzxcL3RkPlxyXG5cdFx0XHQ8dGQ+RDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5OPFwvdGQ+XHJcblx0XHRcdDx0ZD5JPFwvdGQ+XHJcblx0XHRcdDx0ZD5WPFwvdGQ+XHJcblx0XHRcdDx0ZD5BPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHViYWE4XHViNDUwIFx1YWMxOVx1Yzc0MCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzFjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YmE4NyBcdWFjMWNcdWIwOTggXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1ZDU1YyBcdWIyZThcdWM1YjRcdWIyOTQgXHVhZjJkIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWJiMzhcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc0XHViMmU0XHViYTc0LCBcdWI0NTAgXHVkMDZjXHViODVjXHVjMmE0XHVjNmNjXHViNGRjXHVkMzdjXHVjOTkwXHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWQzN2NcdWM5OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg0ICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3M2NcdWJhNzAsIDEwXHVhZTAwXHVjNzkwIFx1Yzc3NFx1YjBiNFx1Yzc3NFx1YjJlNC4mbmJzcDtcdWM3ODVcdWI4MjUgXHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDA2Y1x1Yjg1Y1x1YzJhNFx1YzZjY1x1YjRkYyBcdWQzN2NcdWM5OTBcdWM3NDQgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgwNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJBWkJJQlJJR0EiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBhbHJlYWR5IHNvbHZlZCBhbGwgY3Jvc3N3b3JkcyBhdmFpbGFibGUgaW4gZGFpbHkgbmV3c3BhcGVycywgYW5kIGhlIGlzIHRvbyBpbnRpbWlkYXRlZCBieSBBQ1RBIHRvIGRvd25sb2FkIG5ldyBvbmVzIGZyb20gdGhlIEludGVybmV0LiBOb3cgaGUgaGFzIGFza2VkIEZyYW5lIHRvIGNoYWxsZW5nZSBoaW0gd2l0aCBhIHByb2dyYW1taW5nIHByb2JsZW0uIEZyYW5lIGhhcyBlYWdlcmx5IHJlc3BvbmRlZCB3aXRoIGEgYnJhbmQgbmV3IHRhc2ssIGFuZCB3YXMga2luZCBlbm91Z2ggbm90IHRvIGxvY2sgdGhlIHRhc2sgdW5kZXIgY29weXJpZ2h0IHByb3RlY3Rpb24sIHNvIHlvdSBhcmUgYWxsb3dlZCB0byBhdHRlbXB0IGl0IHRvbyE8XC9wPlxyXG5cclxuPHA+Rm91ciB3b3JkcyB3aXRoIGVxdWFsIGxlbmd0aHMgY2FuIGJlIHB1dCB0b2dldGhlciBpbiBhIHNxdWFyZSBzdWNoIHRoYXQgdHdvIHdvcmRzIG1hcmsgaG9yaXpvbnRhbCBlZGdlcywgd2hpbGUgdGhlIG90aGVyIHR3byBtYXJrIHZlcnRpY2FsIGVkZ2VzLiBIb3Jpem9udGFsIHdvcmRzIGFyZSByZWFkIGxlZnQgdG8gcmlnaHQsIGFuZCB2ZXJ0aWNhbCBvbmVzIGZyb20gdG9wIHRvIGJvdHRvbS4gQ29ybmVyIGxldHRlcnMgYXJlIHNoYXJlZCBieSB0aGUgdHdvIG5laWdoYm91cmluZyBlZGdlcy4gVGhlIGZpZ3VyZSBiZWxvdyBzaG93cyBvbmUgcG9zc2libGUgc3F1YXJlIGNyZWF0ZWQgZnJvbSB3b3JkcyAmbGRxdW87SExBRCZyZHF1bzssICZsZHF1bztOSVZBJnJkcXVvOywgJmxkcXVvO0hTSU4mcmRxdW87LCAmbGRxdW87REVEQSZyZHF1bzs8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGFibGUtY2VudGVyLTIwIHRkLWNlbnRlclwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkg8XC90ZD5cclxuXHRcdFx0PHRkPkw8XC90ZD5cclxuXHRcdFx0PHRkPkE8XC90ZD5cclxuXHRcdFx0PHRkPkQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+UzxcL3RkPlxyXG5cdFx0XHQ8dGQ+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZD4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkPkU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+STxcL3RkPlxyXG5cdFx0XHQ8dGQ+Jm5ic3A7PFwvdGQ+XHJcblx0XHRcdDx0ZD4mbmJzcDs8XC90ZD5cclxuXHRcdFx0PHRkPkQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+TjxcL3RkPlxyXG5cdFx0XHQ8dGQ+STxcL3RkPlxyXG5cdFx0XHQ8dGQ+VjxcL3RkPlxyXG5cdFx0XHQ8dGQ+QTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuXHJcbjxwPllvdXIgdGFzayBpcywgZ2l2ZW4gYSBsaXN0IG9mIGVxdWFsLWxlbmd0aCB3b3JkcywgdG8gY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzcXVhcmVzIHRoYXQgY2FuIGJlIHB1dCB0b2dldGhlciBmcm9tIGEgc3Vic2V0IG9mIHRoZXNlIHdvcmRzLiBZb3UgYXJlIG5vdCBhbGxvd2VkIHRvIHJlcGVhdCBhIHdvcmQgaW4gdGhlIHNhbWUgc3F1YXJlLiBUd28gc3F1YXJlcyBhcmUgZGlmZmVyZW50IGlmIHRoZXkgZGlmZmVyIGluIGF0IGxlYXN0IG9uZSBjaGFyYWN0ZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICg0ICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBsaXN0LjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgd29yZCBjb25zaXN0aW5nIG9ubHkgb2YgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycy48XC9wPlxyXG5cclxuPHA+RWFjaCB3b3JkIHdpbGwgY29udGFpbiBhdCBtb3N0IDEwIGNoYXJhY3RlcnMuIEFsbCB3b3JkcyB3aWxsIGJlIGRpc3RpbmN0IGFuZCBoYXZlIGVxdWFsIGxlbmd0aC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgb2YgZGlzdGluY3Qgc3F1YXJlcy48XC9wPlxyXG5cclxuPHA+Tm90ZTogVGVzdCBkYXRhIHdpbGwgZW5zdXJlIHRoYXQgdGhlIHNvbHV0aW9uIGZpdHMgaW4gYSA2NC1iaXQgaW50ZWdlciBkYXRhIHR5cGUgKGludDY0IGluIFBhc2NhbCwgbG9uZyBsb25nIGluIENcL0MrKykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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