시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB56181348.148%

문제

DNA 분자는 문자의 연속으로 나타낼 수 있으며, 각 글자는 {'A','C','G','T'} 중 하나이다. 즉, 'A', 'ATG', 'GTA'는 모두 서로 다른 DNA 분자를 나타낸다.

은기는 DNA 분자를 연구하는 화학자이고, DNA 분자를 다음과 같이 고칠 수 있다.

  • A ↔ TC (A는 TC로 변할 수 있고, 그 역으로 변할 수도 있다)
  • C ↔ AG
  • G ↔ CT
  • T ↔ GA

은기는 한 DNA 분자를 적절히 고쳐 다른 DNA 분자를 만들려고 한다. 예를 들면, AA → TCA → TAGA → TAT 이다.

은기의 연구실에는 DNA 분자가 N개 있다. 이때, 가능한 모든 쌍에 대해서, 첫 번째 분자를 두 번째 분자로 고칠 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 DNA 분자의 수 N (2 ≤ N ≤ 100)이 주어진다. 분자는 입력으로 주어진 순서대로 1번부터 N번이다.

다음 N개 줄에는 DNA 분자가 한 줄에 하나씩 주어진다. 분자는 'A', 'C', 'G', 'T'로만 이루어져 있고, 길이는 50,000을 넘지 않는다.

출력

각 줄마다 N개의 문자를 N줄에 걸쳐서 출력한다. i번째 줄의 j번째 글자가 '1'인 경우에는 i번째 분자를 j번째 분자로 고칠 수 있다는 뜻이며, '0'인 경우에는 고칠 수 없다는 뜻이다.

예제 입력 1

4
AA
TAT
C
CGTAC

예제 출력 1

1100
1100
0011
0011

예제 입력 2

4
A
C
G
T

예제 출력 2

1000
0100
0010
0001

예제 입력 3

4
AAA
CCC
TATA
CACA

예제 출력 3

1111
1111
1111
1111
W3sicHJvYmxlbV9pZCI6IjEwMDYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzQwXHVhZTMwXHVjNzU4IEROQSBcdWJkODRcdWM3OTAiLCJkZXNjcmlwdGlvbiI6IjxwPkROQSBcdWJkODRcdWM3OTBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YWUwMFx1Yzc5MFx1YjI5NCB7JiMzOTtBJiMzOTssJiMzOTtDJiMzOTssJiMzOTtHJiMzOTssJiMzOTtUJiMzOTt9IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgJiMzOTtBJiMzOTssICYjMzk7QVRHJiMzOTssICYjMzk7R1RBJiMzOTtcdWIyOTQgXHViYWE4XHViNDUwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggRE5BIFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc0MFx1YWUzMFx1YjI5NCBETkEgXHViZDg0XHVjNzkwXHViOTdjIFx1YzVmMFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3OTBcdWM3NzRcdWFjZTAsIEROQSBcdWJkODRcdWM3OTBcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BICZoYXJyOyBUQyAoQVx1YjI5NCBUQ1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YzVlZFx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+QyAmaGFycjsgQUc8XC9saT5cclxuXHQ8bGk+RyAmaGFycjsgQ1Q8XC9saT5cclxuXHQ8bGk+VCAmaGFycjsgR0E8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWIyOTQgXHVkNTVjIEROQSBcdWJkODRcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWNlMFx1Y2NkMCBcdWIyZTRcdWI5NzggRE5BIFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBBQSAmcmFycjsgVENBICZyYXJyOyBUQUdBICZyYXJyOyBUQVQgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWM3NTggXHVjNWYwXHVhZDZjXHVjMmU0XHVjNWQwXHViMjk0IEROQSBcdWJkODRcdWM3OTBcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjg1YyBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEROQSBcdWJkODRcdWM3OTBcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmQ4NFx1Yzc5MFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBETkEgXHViZDg0XHVjNzkwXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZDg0XHVjNzkwXHViMjk0ICYjMzk7QSYjMzk7LCAmIzM5O0MmIzM5OywgJiMzOTtHJiMzOTssICYjMzk7VCYjMzk7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCA1MCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NTggalx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWFjMDAgJiMzOTsxJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHViZDg0XHVjNzkwXHViOTdjIGpcdWJjODhcdWM5ZjggXHViZDg0XHVjNzkwXHViODVjIFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YmE3MCwgJiMzOTswJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDA2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdUQSIsImRlc2NyaXB0aW9uIjoiPHA+RHVicmF2a2EgdGhlIGNoZW1pc3QgZXhhbWluZXMgRE5BIG1vbGVjdWxlcyBpbiBoZXIgbGFib3JhdG9yeS4gRWFjaCBETkEgbW9sZWN1bGUgaXMgcmVwcmVzZW50ZWQgd2l0aCBhIHNlcmllcyBvZiBjaGFyYWN0ZXJzLCB3aGVyZSBlYWNoIGNoYXJhY3RlcnMgaXMgZnJvbSB0aGUgc2V0IHsmbHNxdW87QSZyc3F1bzssICZsc3F1bztDJnJzcXVvOywgJmxzcXVvO0cmcnNxdW87LCAmbHNxdW87VCZyc3F1bzt9LiBUaGVyZWZvcmUsICZsc3F1bztBJnJzcXVvOywgJmxzcXVvO0FURyZyc3F1bzsgYW5kICZsc3F1bztHVEEmcnNxdW87IGFyZSBzZXJpZXMgb2YgY2hhcmFjdGVycyB3aGljaCByZXByZXNlbnQgZGlmZmVyZW50IEROQSBtb2xlY3VsZXMuPFwvcD5cclxuXHJcbjxwPkR1YnJhdmthIGNhbiBwZXJmb3JtIHRoZSBmb2xsb3dpbmcgbXV0YXRpb25zIChhbHRlcmF0aW9ucykgaW4gYW55IHBhcnQgb2YgdGhlIEROQSBtb2xlY3VsZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BICZoYXJyOyBUQyAodGhlcmVmb3JlLCB0aGUgY2hhcmFjdGVyICZsc3F1bztBJnJzcXVvOyBjYW4gYmUgcmVwbGFjZWQgd2l0aCZsc3F1bztUQyZyc3F1bzsgYW5kIHZpY2UgdmVyc2EpPFwvbGk+XHJcblx0PGxpPkMgJmhhcnI7IEFHPFwvbGk+XHJcblx0PGxpPkcgJmhhcnI7IENUPFwvbGk+XHJcblx0PGxpPlQgJmhhcnI7IEdBPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RHVicmF2a2EgdGVuZHMgdG8gdGFrZSBhIGNlcnRhaW4gbW9sZWN1bGUgYW5kIGFsdGVyIGl0IGJ5IHN1Y2Nlc3NpdmVseSBhcHBseWluZyB0aGVzZSBtdXRhdGlvbnMuIFRoaXMgcmVzdWx0cyBpbiBhIGRpZmZlcmVudCBtb2xlY3VsZSwgZm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwPkFBICZyYXJyOyBUQ0EgJnJhcnI7IFRBR0EgJnJhcnI7IFRBVC48XC9wPlxyXG5cclxuPHA+RHVicmF2a2EgY3VycmVudGx5IGhhcyBOIG1vbGVjdWxlcyBpbiBoZXIgbGFib3JhdG9yeS4gV3JpdGUgYSBwcm9ncmFtbWUgdGhhdCB3aWxsLCBmb3IgZWFjaCBwYWlyIG9mIGdpdmVuIG1vbGVjdWxlcywgZGV0ZXJtaW5lIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gZW5kIHVwIHdpdGggdGhlIHNlY29uZCBtb2xlY3VsZSB3aGVuIHN0YXJ0aW5nIGZyb20gdGhlIGZpcnN0IG1vbGVjdWxlIGJ5IGFwcGx5aW5nIHRoZSBtZW50aW9uZWQgbXV0YXRpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIG1vbGVjdWxlcy4gVGhlIG1vbGVjdWxlcyBhcmUgbWFya2VkIHdpdGggbnVtYmVycyBmcm9tIDEgdG8gTi48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgbW9sZWN1bGVzICZuZGFzaDsgc2VyaWVzIG9mIGNoYXJhY3RlcnMgd2hlcmUgZWFjaCBjaGFyYWN0ZXIgaXMgYW4gdXBwZXJjYXNlIGxldHRlciAmbHNxdW87QSZyc3F1bzssICZsc3F1bztDJnJzcXVvOywgJmxzcXVvO0cmcnNxdW87IG9yICZsc3F1bztUJnJzcXVvOy4gRWFjaCBzZXJpZXMgb2YgY2hhcmFjdGVycyBjb25zaXN0cyBvZiBhdCBsZWFzdCBvbmUgYW5kIGF0IG1vc3QgNTAgMDAwIGNoYXJhY3RlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGV4YWN0bHkgTiBjaGFyYWN0ZXJzIGluIGVhY2ggb2YgTiBsaW5lcy4gVGhlIGotdGggY2hhcmFjdGVyIGluIHRoZSBpLXRoIGxpbmUgc2hvdWxkIGJlICZsc3F1bzsxJnJzcXVvOyBpZiBpdCZyc3F1bztzIHBvc3NpYmxlIHRvIGdldCBtb2xlY3VsZSBqIGZyb20gdGhlIG1vbGVjdWxlIGksIG90aGVyd2lzZSBpdCBzaG91bGQgYmUgJmxzcXVvOzAmcnNxdW87LiBZb3UgbXVzdG4mcnNxdW87dCBwcmludCBzcGFjZXMgYmV0d2VlbiBpbmRpdmlkdWFsIGNoYXJhY3RlcnMgaW4gdGhlIHNhbWUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2014 > Final Exam #1 1번