시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB144956239937.964%

문제

상근이는 자신이 만든 폰트를 테스트하기 위한 문장을 만들려고 한다. 폰트에는 알파벳 소문자만 포함되어 있기 때문에, 문장은 알파벳 소문자로 작성해야 한다.

테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다.

사실 문제를 많이 풀어본 사람이라면, 문제를 여기까지 읽어도 무슨 문제인지 감이 잡혀야 한다.

상근이는 단어 N개가 포함되어 있는 사전을 하나 가지고 있다. 테스트 문장은 사전에 포함된 단어만 이용해서 만들 수 있으며, 각 단어는 한 번씩만 사용해야 한다. 또, 단어의 순서는 중요하지 않다. (“uvijek jedem sarmu” 와 “jedem sarmu uvijek”는 같은 문장이다)

상근이가 만들 수 있는 테스트 문장의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다.

출력

상근이가 만들 수 있는 테스트 문장의 개수를 출력한다. 

예제 입력 1

9
the
quick
brown
fox
jumps
over
a
sleazy
dog

예제 출력 1

2

예제 입력 2

3
a
b
c

예제 출력 2

0

예제 입력 3

15
abcdefghijkl
bcdefghijklm
cdefghijklmn
defghijklmno
efghijklmnop
fghijklmnopq
ghijklmnopqr
hijklmnopqrs
ijklmnopqrst
jklmnopqrstu
klmnopqrstuv
lmnopqrstuvw
mnopqrstuvwx
nopqrstuvwxy
opqrstuvwxyz

예제 출력 3

8189
W3sicHJvYmxlbV9pZCI6Ijk5OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZjBcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViOWNjXHViNGUwIFx1ZDNmMFx1ZDJiOFx1Yjk3YyBcdWQxNGNcdWMyYTRcdWQyYjhcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQzZjBcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjljYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYjM4XHVjN2E1XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1YmIzOFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwIDI2XHVhYzFjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjMmU0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWI5Y2VcdWM3NzQgXHVkNDgwXHVjNWI0XHViY2Y4IFx1YzBhY1x1Yjc4Y1x1Yzc3NFx1Yjc3Y1x1YmE3NCwgXHViYjM4XHVjODFjXHViOTdjIFx1YzVlY1x1YWUzMFx1YWU0Y1x1YzljMCBcdWM3N2RcdWM1YjRcdWIzYzQgXHViYjM0XHVjMmE4IFx1YmIzOFx1YzgxY1x1Yzc3OFx1YzljMCBcdWFjMTBcdWM3NzQgXHVjN2ExXHVkNjAwXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlOFx1YzViNCBOXHVhYzFjXHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVjODA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHViYjM4XHVjN2E1XHVjNzQwIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViMmU4XHVjNWI0XHViOWNjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YjJlOFx1YzViNFx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNTI5XHViOWNjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWM5MTFcdWM2OTRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LiAoJmxkcXVvO3V2aWplayBqZWRlbSBzYXJtdSZyZHF1bzsgXHVjNjQwICZsZHF1bztqZWRlbSBzYXJtdSB1dmlqZWsmcmRxdW87XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3YTVcdWM3NzRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHViYjM4XHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgxICZsZTsgTiAmbGU7IDI1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YzkxMVx1YmNmNVx1YjQxOFx1YjI5NCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YmIzOFx1YzdhNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk5OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGT05UIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgSXZpY2EgZ290IGhpbXNlbGYgYSBzdW1tZXIgam9iIGF0IGEgY29tcGFueSB0aGF0IHByb2R1Y2VzIGNvbXB1dGVyIGZvbnRzLiBUaGUgYnJhbmNoIG9mIHRoZSBjb21wYW55IHdoZXJlIEl2aWNhIHdvcmtzIGF0IHNwZWNpYWxpc2VzIGluIHRlc3RpbmcgY29tcHV0ZXIgZm9udHMgYW5kIEl2aWNhJiMzOTtzIHRlYW0gaXMgcmVzcG9uc2libGUgb2YgdGVzdGluZyBvbmx5IGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGV0dGVycyBhcmUgdGVzdGVkIHNvIHRoYXQgdmFyaW91cyBzZW50ZW5jZXMgdXNpbmcgdGhvc2UgbGV0dGVycyBhcmUgcHJpbnRlZCBvdXQgYW5kIHRoZW4gbWFudWFsbHkgKG1vcmUgYWNjdXJhdGVseSwgdmlzdWFsbHkpIGNoZWNrZWQgaWYgZXZlcnl0aGluZyBpcyBhcnJhbmdlZCBwcm9wZXJseS4gT25seSBzZW50ZW5jZXMgd2hpY2ggY29udGFpbiBhbGwgMjYgbG93ZXJjYXNlIGxldHRlciBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCAoYS16KSBhcmUgdXNlZCBmb3IgdGVzdGluZyBwdXJwb3Nlcy4gVGhlc2Ugc2VudGVuY2VzIGFyZSBjYWxsZWQgdGVzdCBzZW50ZW5jZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSYjMzk7dmUgcHJvYmFibHkgYWxyZWFkeSBhc3N1bWVkIHRoYXQgSXZpY2EmIzM5O3Mgam9iIGlzIHRvIGZpbmQgdGVzdCBzZW50ZW5jZXMuIEhlIGhhcyBhIGRpY3Rpb25hcnkgd2hpY2ggY29uc2lzdHMgb2YgTiB3b3JkcyBhbmQgaGFzIHRvIGNhbGN1bGF0ZSBob3cgbWFueSBkaWZmZXJlbnQgdGVzdCBzZW50ZW5jZXMgY2FuIGJlIG1hZGUgb3V0IG9mIHRob3NlIHdvcmRzLiBFdmVyeSB3b3JkIGZyb20gdGhlIGRpY3Rpb25hcnkgY2FuIGJlIHVzZWQgb25seSBvbmNlIGluIHRoZSBzZW50ZW5jZSBhbmQgdGhlIG9yZGVyIG9mIHRoZSB3b3JkcyBpbiB0aGUgc2VudGVuY2UgaXMgaXJyZWxldmFudCAoaS5lLiAmbGRxdW87dXZpamVrIGplZGVtIHNhcm11JnJkcXVvOyBhbmQgJmxkcXVvO2plZGVtIHNhcm11IHV2aWplayZyZHF1bzsgYXJlIGVxdWFsIHNlbnRlbmNlcykuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDI1KSwgdGhlIG51bWJlciBvZiB3b3JkcyBpbiB0aGUgZGljdGlvbmFyeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgd29yZCBmcm9tIHRoZSBkaWN0aW9uYXJ5LCBpdHMgbGVuZ3RoIG5vdCBleGNlZWRpbmcgMTAwLiBBbGwgdGhlIHdvcmRzIGZyb20gdGhlIGRpY3Rpb25hcnkgYXJlIGdvaW5nIHRvIGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgZnJvbSB0aGUgdGFzay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIGZpcnN0IGV4YW1wbGU6IEFsbCB3b3JkcyBidXQgdGhlIHdvcmQgJmxkcXVvO2EmcmRxdW87IG11c3QgYmUgdXNlZCBpbiB0aGUgdGVzdCBzZW50ZW5jZSBiZWNhdXNlIGVhY2ggd29yZCBjb250YWlucyBhIGxldHRlciB0aGF0IGNhbm5vdCBiZSBmb3VuZCBpbiBhbnkgb3RoZXIgd29yZC4gVGhlcmVmb3JlLCB0aGVyZSBhcmUgdHdvIHBvc3NpYmxlIHNvbHV0aW9ucy4gVGhlIGZpcnN0IG9uZSBiZWluZyB0aGUgc2VudGVuY2Ugd2hpY2ggY29uc2lzdHMgb2YgYWxsIHRoZSB3b3JkcyBhbmQgdGhlIHNlY29uZCBvbmUgYmVpbmcgdGhlIHNlbnRlbmNlIHdoaWNoIGNvbnNpc3RzIG9mIGFsbCB0aGUgd29yZHMgYXBhcnQgZnJvbSB0aGUgd29yZCAmbGRxdW87YSZyZHF1bzsuPFwvcD5cclxuXHJcbjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIHRoaXJkIGV4YW1wbGU6IEdpdmVuIHRoYXQgdGhlIGV4YW1wbGUgaXMgbG9uZywgd2Ugc3RyZXNzIHRoYXQgYWxsIHRoZSB3b3JkcyBmcm9tIHRoZSBleGFtcGxlIGNvbnNpc3Qgb2YgY29uc2VjdXRpdmUgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #6 2번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: kcm1700