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

문제

R개의 행과 C개의 열로 이루어진 테이블이 입력으로 주어진다. 이 테이블의 원소는 알파벳 소문자이다.

각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있다. 예제 입력에서

dobarz
adatak

이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 된다.

만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을 지워주고, count의 개수를 1 증가시키는, 이 과정을 반복한다. 만약 동일한 문자열이 발견되는 경우, 반복을 멈추고 count의 개수를 출력 후 프로그램을 종료한다.

테이블이 주어질 경우 count의 값을 구해보자.

입력

첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000)

이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않는 입력만 주어진다.

출력

문제의 설명과 같이 count의 값을 출력한다.

예제 입력 1

2 6
dobarz
adatak

예제 출력 1

0

예제 입력 2

3 4
alfa
beta
zeta

예제 출력 2

2

예제 입력 3

4 6
mrvica
mrvica
marica
mateja

예제 출력 3

1
W3sicHJvYmxlbV9pZCI6IjI4NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjNzk4XHViNzdjXHViMGI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5SXHVhYzFjXHVjNzU4IFx1ZDU4OVx1YWNmYyBDXHVhYzFjXHVjNzU4IFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMTRjXHVjNzc0XHViZTE0XHVjNzc0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM3NTggXHVjNmQwXHVjMThjXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWM3NzRcdWJlMTRcdWM3NTggXHVjNWY0XHVjNzQ0IFx1YzcwNFx1YzVkMFx1YzExYyBcdWM1NDRcdWI3OThcdWI4NWMgXHVjNzdkXHVjNWI0XHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWM8XC9wPlxyXG5cclxuPHByZT5cclxuZG9iYXJ6XHJcbmFkYXRhazxcL3ByZT5cclxuXHJcbjxwPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwICZxdW90O2RhJnF1b3Q7LCAmcXVvdDtvZCZxdW90OywgJnF1b3Q7YmEmcXVvdDssICZxdW90O2F0JnF1b3Q7LCAmcXVvdDtyYSZxdW90OywgJnF1b3Q7emsmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzc0IDZcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHViNGU0XHVjNzc0IFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNzU4Jm5ic3A7XHVkNTg5XHVjNzQ0IFx1YzljMFx1YzZjY1x1YjNjNCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM3NTggXHVjNWY0XHVjNzQ0IFx1Yzc3ZFx1YzViNFx1YzExYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgXHVhYzAwXHVjN2E1IFx1YzcwNFx1Yzc1OCBcdWQ1ODlcdWM3NDQgXHVjOWMwXHVjNmNjXHVjOGZjXHVhY2UwLCBjb3VudFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgMSBcdWM5OWRcdWFjMDBcdWMyZGNcdWQwYTRcdWIyOTQsIFx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWJjMWNcdWFjYWNcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwLCBcdWJjMThcdWJjZjVcdWM3NDQmbmJzcDtcdWJhNDhcdWNkOTRcdWFjZTAgY291bnRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNSBcdWQ2YzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjNzc0XHViZTE0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWFjYmRcdWM2YjAgY291bnRcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1Yzc3NFx1YmUxNFx1Yzc1OCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzggUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMiAmbGU7IFIsIEMgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgUlx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgQ1x1YWMxY1x1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWQxNGNcdWM3NzRcdWJlMTRcdWM1ZDBcdWIyOTQgXHVjNWY0XHVjNzQ0IFx1Yzc3ZFx1YzViNFx1YzExYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YjU0YywgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Yzc4NVx1YjgyNVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1YzEyNFx1YmE4NVx1YWNmYyBcdWFjMTlcdWM3NzQmbmJzcDtjb3VudFx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4NjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaTkFOU1RWRU5JSyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhpcyBlY29ub215LCB3ZSBhbGwga25vdyBob3cgaGFyZCBpdCBpcyB0byBnZXQgYSBqb2IuIE1pcmtvLCBhIHJlY2VudCBjb2xsZWdlIGdyYWR1YXRlLCBob3dldmVyLCBnb3QgbHVja3kgLSBoZSBpcyBub3cgZW1wbG95ZWQgYXMgYSBydW5lb2xvZ2lzdCBieSB0aGUgTGFuZ3VhZ2UgSW5zdGl0dXRlIG9mIENyb2F0aWEuIEhpcyBmcmllbmQgU2xhdmtvIGJlbGlldmVzIHJ1bmVvbG9neSBpc24mcnNxdW87dCBhIHNjaWVuY2UgYW5kIGlzIGhlbmNlIGFuZ3J5IGF0IE1pcmtvIGZvciBiZWxpZXZpbmcgdGhlIG9wcG9zaXRlLiBPbmUgZm9nZ3kgQ2hyaXN0bWFzIGRheSwgTWlya28mcnNxdW87cyBsYXB0b3AgYnJva2UuIFNpbmNlIGhlIGlzbiZyc3F1bzt0IGdyZWF0IHdpdGggY29tcHV0ZXJzLCBoZSBnYXZlIGl0IHRvIFNsYXZrbyB0byByZXBhaXIgaXQuIFNsYXZrbywgZmVsbGluZyBhIGxpdHRsZSBuYXVnaHR5LCBkZWNpZGVkIHRvIG1lc3MgdXAgYSBwYXJ0aWN1bGFyIGZpbGUgTWlya28gd2FzIHdvcmtpbmcgb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoaXMgZmlsZSBjb250YWlucyBhIG1hdHJpeCBvZiBSIHJvd3MgYW5kIEMgY29sdW1ucy4gRWFjaCBlbGVtZW50IG9mIHRoZSBtYXRyaXggaXMgYSBzaW5nbGUgbGV0dGVyLiBObyB0d28gY29sdW1ucyBvZiB0aGUgbWF0cml4IGFyZSBlcXVhbC4gVG8gaGF2ZSBzb21lIGZ1biB3aXRoIHBzZXVkby1zY2llbnRpc3QgTWlya28sIFNsYXZrbyBkZWNpZGVkIGhlIHdpbGwgZGVsZXRlIGFzIG11Y2ggcm93cyBhcyBwb3NzaWJsZSBmcm9tIHRoZSB0b3Agb2YgdGhlIHRhYmxlLCB3aXRob3V0IGJyZWFraW5nIHRoZSBuby1lcXVhbC1jb2x1bW4gcnVsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDICgyICZsZTsgUiwgQyAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIHRoZSBudW1iZXIgb2YgY29sdW1ucywgcmVzcGVjdGl2ZWx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBlYWNoIG9mIHRoZSBuZXh0IFIgbGluZXMgdGhlcmUgYXJlIEMgc21hbGwgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gVGhlc2UgUiB4IEMgbGV0dGVycyByZXByZXNlbnQgTWlya28mcnNxdW87cyB0YWJsZSAod2hpY2ggZG9lcyBub3QgaGF2ZSB0d28gc2FtZSBjb2x1bW5zKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlciwgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvd3Mgd2hpY2ggY2FuIGJlIGRlbGV0ZWQgZnJvbSB0aGUgdG9wIG9mIHRoZSB0YWJsZSBzbyB0aGF0IG5vIHR3byBjb2x1bW5zIGFyZSBlcXVhbC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #3 4번