시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 72 29 23 40.351%

문제

리트는 알파벳을 다른 기호로 바꿔서 적는 방법으로, 주로 인터넷에서 사용한다. 영어 알파벳의 각 문자는 비슷하게 생긴 하나 또는 그 이상의 문자로 바꿔서 적는다. 예를 들어, ACMICPC에서 A를 4, C를 (, M을 |V|, I를 1, P를 |>로 바꾸면, "4(IVI1(|>(" 로 적을 수 있다. M과 P의 경우처럼 한 알파벳을 길이가 1보다 큰 문자로 바꿀 수도 있다.

한 알파벳을 다른 문자로 바꾸는 방법이 여러 가지일 수도 있다. 예를 들어, D를 나타낼 때 [), |), |> 를 사용할 수 있다. 이러한 점들 때문에, Leet는 매우 읽기 어렵다.

영어 알파벳으로 적혀있는 원래 단어와 리트로 적혀진 단어가 주어졌을 때, 두 단어가 아래 조건을 지키는지 아닌지를 검사하는 프로그램을 작성하시오.

  1. 각 알파벳을 리트로 나타낼 때, 최대 k개의 문자로 바꿀 수 있다. k는 입력으로 주어진다.
  2. 한 알파벳을 리트로 바꾸는 방법은 한 가지이다. 예를 들어, D의 리트로 [)를 사용하는 경우에는 |>를 D의 리트로 사용할 수 없다.
  3. 두 개 또는 그 이상의 알파벳을 리트로 바꿨을 때, 그 결과가 같을 수도 있다. 예를 들어, D와 P의 리트가 동시에 |>일 수도 있다.
  4. 알파벳과 리트가 서로 비슷하게 보이지 않아도 상관없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 한 알파벳을 리트로 바꿨을 때 리트의 최대 길이 k가 주어진다. (1 ≤ k ≤ 3) 둘째 줄에는 원래 단어가 주어진다. 단어는 알파벳 소문자 a-z로만 이루어져 있고, 길이는 1보다 크거나 같고, 15보다 작거나 같다. 셋째 줄에는 리트로 나타낸 단어가 주어진다. 리트의 길이는 1보다 크거나 같으며, a-z, A-Z, 0-9, @, \, /, -, =, ^, |, [, ], (, ), {, }, <, >로 이루어져 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 단어가 같으면 1, 아니면 0을 출력한다.

예제 입력 1

2
3
mississippi
nni55i55ippi
2
foobar
|=o08ar

예제 출력 1

1
0
W3sicHJvYmxlbV9pZCI6Ijg5MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YWNcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjlhY1x1ZDJiOFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHViMmU0XHViOTc4IFx1YWUzMFx1ZDYzOFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHVjODAxXHViMjk0IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YywgXHVjOGZjXHViODVjIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YzYwMVx1YzViNCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMgXHVjMGRkXHVhZTM0IFx1ZDU1OFx1YjA5OCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHViYzE0XHVhZmQ0XHVjMTFjIFx1YzgwMVx1YjI5NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQUNNSUNQQ1x1YzVkMFx1YzExYyBBXHViOTdjIDQsIENcdWI5N2MgKCwgTVx1Yzc0NCB8VnwsIElcdWI5N2MgMSwgUFx1Yjk3YyB8Jmd0O1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWJhNzQsICZxdW90OzQoSVZJMSh8Jmd0OygmcXVvdDsgXHViODVjIFx1YzgwMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBNXHVhY2ZjIFBcdWM3NTggXHVhY2JkXHVjNmIwXHVjYzk4XHViN2ZjIFx1ZDU1YyBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTVjIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBEXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWI1NGMgWyksIHwpLCB8Jmd0OyBcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWM4MTBcdWI0ZTQgXHViNTRjXHViYjM4XHVjNWQwLCBMZWV0XHViMjk0IFx1YjllNFx1YzZiMCBcdWM3N2RcdWFlMzAgXHVjNWI0XHViODM1XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDFcdWM1YjQgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzNjXHViODVjIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM2ZDBcdWI3OTggXHViMmU4XHVjNWI0XHVjNjQwIFx1YjlhY1x1ZDJiOFx1Yjg1YyBcdWM4MDFcdWQ2MDBcdWM5YzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNTQ0XHViNzk4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWIyOTRcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YWM4MFx1YzBhY1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YWMwMSBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHViOWFjXHVkMmI4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBrXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4ga1x1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQ1NWMgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YjlhY1x1ZDJiOFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1ZDU1YyBcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIERcdWM3NTggXHViOWFjXHVkMmI4XHViODVjIFspXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgfCZndDtcdWI5N2MgRFx1Yzc1OCBcdWI5YWNcdWQyYjhcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1MCBcdWFjMWMgXHViNjEwXHViMjk0IFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YjlhY1x1ZDJiOFx1Yjg1YyBcdWJjMTRcdWFmZThcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YWMxOVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBEXHVjNjQwIFBcdWM3NTggXHViOWFjXHVkMmI4XHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCB8Jmd0O1x1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NGNcdWQzMGNcdWJjYjNcdWFjZmMgXHViOWFjXHVkMmI4XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMgXHViY2Y0XHVjNzc0XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YjlhY1x1ZDJiOFx1Yjg1YyBcdWJjMTRcdWFmZThcdWM3NDQgXHViNTRjIFx1YjlhY1x1ZDJiOFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhZTM4XHVjNzc0IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGsgJmxlOyAzKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZkMFx1Yjc5OCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCBhLXpcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTVcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YWNcdWQyYjhcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjlhY1x1ZDJiOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBhLXosIEEtWiwgMC05LCBALCBcXCwgXC8sIC0sID0sIF4sIHwsIFssIF0sICgsICksIHssIH0sICZsdDssICZndDtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVhYzE5XHVjNzNjXHViYTc0IDEsIFx1YzU0NFx1YjJjOFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGVldCIsImRlc2NyaXB0aW9uIjoiPHA+TGVldCBpcyBhbiBhbHRlcm5hdGl2ZSBFbmdsaXNoIGFscGhhYmV0IHVzZWQgbW9zdGx5IG9uIHRoZSBJbnRlcm5ldC4gRWFjaCBjaGFyYWN0ZXIgaW4gdGhlIEVuZ2xpc2ggYWxwaGFiZXQgaXMgcmVwbGFjZWQgYnkgb25lIG9yIG1vcmUgY2hhcmFjdGVycyB3aGljaCBsb29rIHNpbWlsYXIgdG8gdGhlIG9yaWdpbmFsIG9uZS4gRm9yIGV4YW1wbGUsIHRoZSBwaHJhc2UgQUNNSUNQQyBjYW4gYmUgd3JpdHRlbiBhcyA0KHxWfDEofCZndDsoIGluIExlZXQgYnkgcmVwbGFjaW5nIEEgd2l0aCA0LCBDIHdpdGggKCwgTSB3aXRoIHxWfCwgSSB3aXRoIDEsIGFuZCBQIHdpdGggfCZndDsuIE5vdGUgdGhhdCB0aHJlZSBzeW1ib2xzIHxWfCB3ZXJlIHVzZWQgdG8gcmVwcmVzZW50IGEgc3ltYm9sIE0gYW5kIHR3byBzeW1ib2xzIHwmZ3Q7IGZvciBQLjxcL3A+XHJcblxyXG48cD5UaGVyZSBtYXkgYmUgbW9yZSB0aGFuIG9uZSB3YXkgdG8gcmVwcmVzZW50IGFuIEVuZ2xpc2ggY2hhcmFjdGVyLiBGb3IgZXhhbXBsZSwgWyksIHwpLCBhbmQgfCZndDsgbWF5IHJlcHJlc2VudCBELiBXaGlsZSBpbnRlcmVzdGluZywgTGVldCBjYW4gYmUgdmVyeSBjb25mdXNpbmcgYW5kIGhhcmQgdG8gcmVhZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gb25lIHNlbnRlbmNlIGluIHRoZSBTdGFuZGFyZCBFbmdsaXNoIGFscGhhYmV0IGFuZCBhbm90aGVyIGluIExlZXQsIHdyaXRlIGEgcHJvZ3JhbSB0byBkZWNpZGUgd2hldGhlciB0aGV5IGFyZSB0aGUgc2FtZSBvciBub3QgdW5kZXIgdGhlIGZvbGxvd2luZyBydWxlcy4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5FYWNoIGNoYXJhY3RlciBpbiB0aGUgU3RhbmRhcmQgRW5nbGlzaCBhbHBoYWJldCBpcyBtYXBwZWQgdG8gdXAgdG8gayBjaGFyYWN0ZXJzIGluIExlZXQuIFRoZSB2YWx1ZSBvZiBrIGlzIGtub3duIGluIGFkdmFuY2UuPFwvbGk+XHJcblx0PGxpPkZvciBlYWNoIGNoYXJhY3RlciBpbiB0aGUgU3RhbmRhcmQgRW5nbGlzaCBhbHBoYWJldCwgdGhlcmUgaXMgb25seSBvbmUgd2F5IHRvIHJlcHJlc2VudCBpdCBpbiBMZWV0LiBGb3IgZXhhbXBsZSwgb25jZSBEIGlzIG1hcHBlZCB0byBbKSwgdGhlbiB5b3UgY2Fubm90IHVzZSB8Jmd0OyB0byByZXByZXNlbnQgRCB3aXRoaW4gdGhlIHNhbWUgcGhyYXNlLiBCdXQgdHdvIG9yIG1vcmUgY2hhcmFjdGVycyBvZiB0aGUgU3RhbmRhcmQgRW5nbGlzaCBhbHBoYWJldCBjYW4gYmUgbWFwcGVkIHRvIHRoZSBzYW1lIHNlcXVlbmNlIG9mIHN5bWJvbChzKSBpbiBMZWV0LiBGb3IgZXhhbXBsZSwgYm90aCBEIGFuZCBQIGNhbiBiZSBtYXBwZWQgdG8gfCZndDsgc2ltdWx0YW5lb3VzbHkuIEFuIEVuZ2xpc2ggY2hhcmFjdGVyIGFuZCBpdHMgTGVldCByZXByZXNlbnRhdGlvbiBkbyBub3QgbmVlZCB0byBsb29rIHNpbWlsYXIgdG8gZWFjaCBvdGhlci4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0aHJlZSBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgb25lIGludGVnZXIgayAoMSAmbGU7IGsgJmxlOyAzKSB3aGljaCBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgY2hhcmFjdGVycyBpbiBMZWV0IGZvciBvbmUgU3RhbmRhcmQgRW5nbGlzaCBhbHBoYWJldC4gVGhlIHNlY29uZCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIGEgcGhyYXNlIGluIFN0YW5kYXJkIEVuZ2xpc2ggd2hvc2UgbGVuZ3RoIGlzIGJldHdlZW4gMSBhbmQgMTUsIGluY2x1c2l2ZS4gSXQgaXMgd3JpdHRlbiBpbiBFbmdsaXNoIGxvd2VyY2FzZSBhLXouIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIGEgcGhyYXNlIGluIExlZXQgd2hvc2UgbGVuZ3RoIGlzIGVxdWFsIHRvIG9yIGdyZWF0ZXIgdGhhbiAxLiBJdCBpcyB3cml0dGVuIGluIHByaW50YWJsZSBzeW1ib2xzIGEteiwgQS1aLCAwLTksIEAsIFxcLCBcLywgLSwgPSwgXiwgfCwgWywgXSAsICgsICkgLCB7LCB9LCAmbHQ7LCBhbmQgJmd0Oy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gZWl0aGVyIDAgb3IgMS4gUHJpbnQgMSBpZiB0d28gaW5wdXQgc3RyaW5ncyBhcmUgdGhlIHNhbWUuIE90aGVyd2lzZSBwcmludCAwLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 F번