시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 80 42 40 58.824%

문제

C 언어 프로그래밍에서 문자열(string)은 native한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다 : 그들 중에는 strcpystrcmpstrtolstrtokstrlen, strcat 가 있다.

하지만, 잘 알려져 있지 않으며, 잘 사용되지도 않는 함수가 하나 있다 : strfry 함수다. strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요는 없다.)

두 개의 문자열에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지 판단하라.

입력

입력의 첫 번째 줄은 테스트 케이스의 수 0 < N < 1001 이다.

각각의 테스트 케이스는 하나의 줄에 영어 소문자들로만 이루어진 두 개의 문자열이 한 개의 공백으로 구분되어 주어진다. 각각의 문자열의 길이는 최대 1000 이다.

출력

각각의 테스트 케이스에 대해, 2번째 문자열이 1번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지의 여부를 "Impossible"(불가능) 또는 "Possible"(가능)으로 나타내시오. (따옴표는 제외하고 출력한다.)

예제 입력 1

4
a a
ab ba
ring gnir
newt twan

예제 출력 1

Possible
Possible
Possible
Impossible
W3sicHJvYmxlbV9pZCI6IjExMzI4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiU3RyZnJ5IiwiZGVzY3JpcHRpb24iOiI8cD5DIFx1YzViOFx1YzViNCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGRcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHVjNWY0KHN0cmluZylcdWM3NDAgbmF0aXZlXHVkNTVjIFx1Yzc5MFx1YjhjY1x1ZDYxNVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzBhY1x1YzJlNCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YWRmOFx1YzgwMCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWQ0NWNcdWMyZGNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YjlkMFx1YjJlOFx1Yzc1OCBOVUxMXHVjNzc0IFx1YzBhY1x1YzZhOVx1YjQxYywgXHViYjM4XHVjNzkwXHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3N2MgXHViZmQwXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YzViOFx1YzViNFx1YzVkMFx1YzExYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViMmU0XHViOGU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjOTExXHVjNjk0XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgQyBcdWQ0NWNcdWM5MDAgXHViNzdjXHVjNzc0XHViZTBjXHViN2VjXHViOWFjXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWIyZTRcdWI4ZThcdWIyOTQgXHViMzcwXHVjNWQwIFx1YjllNFx1YzZiMCBcdWM3MjBcdWM2YTlcdWQ1NWMgXHVkNTY4XHVjMjE4XHViNGU0XHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQgOiBcdWFkZjhcdWI0ZTQgXHVjOTExXHVjNWQwXHViMjk0Jm5ic3A7PHN0cm9uZz5zdHJjcHk8XC9zdHJvbmc+LCZuYnNwOzxzdHJvbmc+c3RyY21wPFwvc3Ryb25nPiwmbmJzcDs8c3Ryb25nPnN0cnRvbDxcL3N0cm9uZz4sJm5ic3A7PHN0cm9uZz5zdHJ0b2s8XC9zdHJvbmc+LCZuYnNwOzxzdHJvbmc+c3RybGVuPFwvc3Ryb25nPiwgPHN0cm9uZz5zdHJjYXQ8XC9zdHJvbmc+Jm5ic3A7XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3OTggXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1Yzc5OCBcdWMwYWNcdWM2YTlcdWI0MThcdWM5YzBcdWIzYzQgXHVjNTRhXHViMjk0IFx1ZDU2OFx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOTggXHVjNzg4XHViMmU0IDombmJzcDs8c3Ryb25nPnN0cmZyeTxcL3N0cm9uZz4mbmJzcDtcdWQ1NjhcdWMyMThcdWIyZTQuJm5ic3A7PHN0cm9uZz5zdHJmcnk8XC9zdHJvbmc+Jm5ic3A7XHVkNTY4XHVjMjE4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViYjM0XHVjNzkxXHVjNzA0XHViODVjIFx1YzdhY1x1YmMzMFx1YzVmNFx1ZDU1OFx1YzVlYyBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YjBiOFx1YjJlNC4gKFx1YzVlZFx1Yzc5MCBcdWM4ZmMgOiBcdWM1ZWNcdWFlMzBcdWM1ZDBcdWMxMWMgXHVjNzg1XHViODI1XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YWNmYyBcdWMwYzhcdWI4NWMgXHVjN2FjXHViYzMwXHVjNWY0XHViNDFjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWIyZTRcdWI5N2MgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgMlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgMVx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAmbmJzcDs8c3Ryb25nPnN0cmZyeTxcL3N0cm9uZz4mbmJzcDtcdWQ1NjhcdWMyMThcdWI5N2MgXHVjODAxXHVjNmE5XHVkNTU4XHVjNWVjIFx1YzViYlx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YjJlOFx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCZuYnNwOzAgJmx0OyZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz4mbmJzcDsmbHQ7IDEwMDEgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWI0ZTRcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDU1YyBcdWFjMWNcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDAwIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsJm5ic3A7Mlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgMVx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAmbmJzcDs8c3Ryb25nPnN0cmZyeTxcL3N0cm9uZz4mbmJzcDtcdWQ1NjhcdWMyMThcdWI5N2MgXHVjODAxXHVjNmE5XHVkNTU4XHVjNWVjIFx1YzViYlx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHVjNzU4IFx1YzVlY1x1YmQ4MFx1Yjk3YyAmcXVvdDtJbXBvc3NpYmxlJnF1b3Q7KFx1YmQ4OFx1YWMwMFx1YjJhNSkgXHViNjEwXHViMjk0ICZxdW90O1Bvc3NpYmxlJnF1b3Q7KFx1YWMwMFx1YjJhNSlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjMmRjXHVjNjI0LiAoXHViNTMwXHVjNjM0XHVkNDVjXHViMjk0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMzI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyZnJ5IiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgQyBwcm9ncmFtbWluZyBsYW5ndWFnZSwgc3RyaW5ncyBhcmUgbm90IGEgbmF0aXZlIGRhdGEgdHlwZS4gSW4gZmFjdCwgdGhleSBhcmUganVzdCBhbiBhcnJheSBvZiBjaGFyYWN0ZXJzLCB3aXRoIGEgc2VudGluZWwgTlVMTCB2YWx1ZSB1c2VkIHRvIGRlbm90ZSB0aGUgZW5kIG9mIHRoZSBzdHJpbmcuIFNpbmNlIHdvcmtpbmcgd2l0aCBzdHJpbmdzIGlzIGEgdmVyeSBpbXBvcnRhbnQgdGhpbmcgdG8gZG8gaW4gcHJvZ3JhbW1pbmcgbGFuZ3VhZ2VzLCB0aGUgQyBzdGFuZGFyZCBsaWJyYXJ5IGhhcyBzZXZlcmFsIHZlcnkgdXNlZnVsIGZ1bmN0aW9ucyBmb3Igc3RyaW5nIG1hbmlwdWxhdGlvbjogYW1vbmcgdGhlbSBhcmUmbmJzcDs8c3Ryb25nPnN0cmNweTxcL3N0cm9uZz4sJm5ic3A7PHN0cm9uZz5zdHJjbXA8XC9zdHJvbmc+LCZuYnNwOzxzdHJvbmc+c3RydG9sPFwvc3Ryb25nPiwmbmJzcDs8c3Ryb25nPnN0cnRvazxcL3N0cm9uZz4sJm5ic3A7PHN0cm9uZz5zdHJsZW48XC9zdHJvbmc+LCBhbmQmbmJzcDs8c3Ryb25nPnN0cmNhdDxcL3N0cm9uZz4uPFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIHRoZXJlIGlzIG9uZSBmdW5jdGlvbiB0aGF0IG5vdCBtYW55IGtub3cgYWJvdXQsIGFuZCBldmVuIGZld2VyIHVzZSBpdDogdGhlJm5ic3A7PHN0cm9uZz5zdHJmcnk8XC9zdHJvbmc+Jm5ic3A7ZnVuY3Rpb24uJm5ic3A7PHN0cm9uZz5zdHJmcnk8XC9zdHJvbmc+Jm5ic3A7dGFrZXMgYW4gaW5wdXQgc3RyaW5nIGFuZCByYW5kb21seSBzd2FwcyBhIHJhbmRvbSBudW1iZXIgb2YgY2hhcmFjdGVycy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdHdvIHN0cmluZ3MsIGRldGVybWluZSBpZiBpdCBpcyBwb3NzaWJsZSB0aGF0IHRoZSBzZWNvbmQgc3RyaW5nIGlzIHRoZSBmaXJzdCBzdHJpbmcsIHN0cmZyaWVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGJlZ2lucyB3aXRoIGEgbnVtYmVyIDAgJmx0OyZuYnNwOzxzdHJvbmc+TjxcL3N0cm9uZz4mbmJzcDsmbHQ7IDEwMDEsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHR3byBzdHJpbmdzIG9mIGxvd2VyY2FzZSBFbmdsaXNoIGNoYXJhY3RlcnMsIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZTsgdGhlc2UgYXJlIHRoZSB0d28gc3RyaW5ncyBpbiBxdWVzdGlvbi4gRWFjaCBzdHJpbmcgaXMgYXQgbW9zdCAxMDAwIGNoYXJhY3RlcnMgbG9uZy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLCBjb250YWluaW5nIGVpdGhlciAmcXVvdDtJbXBvc3NpYmxlJnF1b3Q7IG9yICZxdW90O1Bvc3NpYmxlJnF1b3Q7ICh3aXRob3V0IHF1b3RlcykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2014 E번

  • 문제를 번역한 사람: veydpz