시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 371 220 193 63.487%

문제

한신이는 대학교에서 "복붙의 달인"으로 유명하다. 한신이는 타이핑 속도가 느리기 때문에 대학에서 가능한 모든 일을 복붙으로 해결한다. 그는 n개의 문자를 입력하는데 있어서 n초의 시간이 걸리지만 뛰어난 "붙여넣기" 스킬을 이용하면 어떠한 개수의 문자도 단 1초만에 타이핑 할 수 있다. 만약 한신이가 "bana"를 복사한 상태에서 "banana"를 타이핑한다면, "bana" 붙여넣기 1초, 'n' 입력, 'a' 입력으로 총 3초가 걸린다. 한신이가 클립보드에 저장한 p를 알고 있을 때 s를 입력하는데 걸리는 최소 시간을 계산해보자!

입력

첫 번째 줄에는 테스트케이스의 개수 T(T ≤ 25)가 입력된다. 각 테스트케이스는 한 줄에 2개의 문자열 s와 p가 공백으로 구분되어 입력되며 한신이는 p를 복사하여 s를 만들어 내는 것을 목표로 한다. s의 최대 길이는 10,000이고, p의 최대 길이는 100이다.

출력

각 테스트 케이스에 맞는 한신이가 p를 이용하여 s를 타이핑할 때 걸리는 최소 시간(초 단위)을 출력하라!

예제 입력 1

2
banana bana
asakusa sa

예제 출력 1

3
5
W3sicHJvYmxlbV9pZCI6IjExMDA4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViY2Y1XHViZDk5XHVjNzU4IFx1YjJlY1x1Yzc3OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTVjXHVjMmUwXHVjNzc0XHViMjk0IFx1YjMwMFx1ZDU1OVx1YWQ1MFx1YzVkMFx1YzExYyZuYnNwOyZxdW90O1x1YmNmNVx1YmQ5OVx1Yzc1OCBcdWIyZWNcdWM3NzgmcXVvdDtcdWM3M2NcdWI4NWMgXHVjNzIwXHViYTg1XHVkNTU4XHViMmU0LiBcdWQ1NWNcdWMyZTBcdWM3NzRcdWIyOTQmbmJzcDtcdWQwYzBcdWM3NzRcdWQ1NTEgXHVjMThkXHViM2M0XHVhYzAwIFx1YjI5MFx1YjlhY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWIzMDBcdWQ1NTlcdWM1ZDBcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM3N2NcdWM3NDQgXHViY2Y1XHViZDk5XHVjNzNjXHViODVjIFx1ZDU3NFx1YWNiMFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWFkZjhcdWIyOTQgblx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1Yzc4OFx1YzViNFx1YzExYyBuXHVjZDA4XHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWM5YzBcdWI5Y2MmbmJzcDtcdWI2ZjBcdWM1YjRcdWIwOWMmbmJzcDsmcXVvdDtcdWJkOTlcdWM1ZWNcdWIxMjNcdWFlMzAmcXVvdDsgXHVjMmE0XHVkMGFjXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCZuYnNwO1x1YzViNFx1YjVhMFx1ZDU1YyBcdWFjMWNcdWMyMThcdWM3NTggXHViYjM4XHVjNzkwXHViM2M0IFx1YjJlOCAxXHVjZDA4XHViOWNjXHVjNWQwIFx1ZDBjMFx1Yzc3NFx1ZDU1MSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDU1Y1x1YzJlMFx1Yzc3NFx1YWMwMCAmcXVvdDtiYW5hJnF1b3Q7XHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU1YyBcdWMwYzFcdWQwZGNcdWM1ZDBcdWMxMWMmbmJzcDsmcXVvdDtiYW5hbmEmcXVvdDtcdWI5N2MgXHVkMGMwXHVjNzc0XHVkNTUxXHVkNTVjXHViMmU0XHViYTc0LCAmcXVvdDtiYW5hJnF1b3Q7IFx1YmQ5OVx1YzVlY1x1YjEyM1x1YWUzMCAxXHVjZDA4LCAmIzM5O24mIzM5OyBcdWM3ODVcdWI4MjUsICYjMzk7YSYjMzk7IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWNkMWQgM1x1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuJm5ic3A7XHVkNTVjXHVjMmUwXHVjNzc0XHVhYzAwIFx1ZDA3NFx1YjliZFx1YmNmNFx1YjRkY1x1YzVkMCBcdWM4MDBcdWM3YTVcdWQ1NWMmbmJzcDtwXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjIHNcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU3NFx1YmNmNFx1Yzc5MCE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVChUICZsZTsgMjUpXHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIDJcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0IHNcdWM2NDAgcFx1YWMwMCZuYnNwO1x1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg1XHViODI1XHViNDE4XHViYTcwJm5ic3A7XHVkNTVjXHVjMmUwXHVjNzc0XHViMjk0IHBcdWI5N2MgXHViY2Y1XHVjMGFjXHVkNTU4XHVjNWVjIHNcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0IFx1YjBiNFx1YjI5NCZuYnNwO1x1YWM4M1x1Yzc0NCBcdWJhYTlcdWQ0NWNcdWI4NWMgXHVkNTVjXHViMmU0LiZuYnNwO3NcdWM3NTggXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NFx1YjI5NCAxMCwwMDBcdWM3NzRcdWFjZTAsIHBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxJm5ic3A7XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWI5ZGVcdWIyOTQgXHVkNTVjXHVjMmUwXHVjNzc0XHVhYzAwIHBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIHNcdWI5N2MgXHVkMGMwXHVjNzc0XHVkNTUxXHVkNTYwIFx1YjU0YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNChcdWNkMDgmbmJzcDtcdWIyZThcdWM3MDQpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3YyE8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTAwOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlR5cGluZyIsImRlc2NyaXB0aW9uIjoiPHA+Q2F0aHkmcnNxdW87cyB0eXBpbmcgc3BlZWQgaXMgbm90IGZhc3QsIGhvd2V2ZXIsIGl0IGlzIHZlcnkgc3RlYWR5LiBTaGUgc3Ryb2tlcyB0aGUga2V5Ym9hcmQgZXhhY3Qgb25jZSBwZXIgc2Vjb25kLCBhbmQgc2hlIGFsd2F5cyBwcmVzc2VzIHRoZSBrZXlzIGNvcnJlY3RseS4gV2l0aG91dCBpbnRlcmZlcmluZywgQ2F0aHkgaGFzIHRvIHNwZW5kIG4gc2Vjb25kcyB0byB0eXBlIGEgc3RyaW5nIHMgb2YgbiBjaGFyYWN0ZXJzLiBJbiBvcmRlciB0byByZWR1Y2UgdGhlIHRpbWUgc3BlbnQgZm9yIHR5cGluZywgQ2F0aHkgY29waWVkIGEgc3RyaW5nIHAgdG8gdGhlIGNsaXBib2FyZC4gVGhlcmVmb3JlLCBzaGUgY2FuIHVzZSB0aGUgJmxkcXVvO3Bhc3RlJnJkcXVvOyBmdW5jdGlvbiB0byBpbnB1dCBtYW55IGNoYXJhY3RlcnMuIEFzc3VtZSB0aGF0IHBhc3RpbmcgcCBhbHNvIHRha2VzIG9ubHkgb25lIGtleWJvYXJkIHN0cm9rZSBmb3IgQ2F0aHkuIElmIENhdGh5IGNvcGllZCBiYW5hIGJlZm9yZSB0eXBpbmcgYmFuYW5hLCB0aGVuIENhdGh5IGNhbiBmaW5pc2ggaXQgaW4gMyBzZWNvbmRzOiBwYXN0aW5nIGJhbmEsIHRoZW4gcHJlc3NpbmcgbiwgdGhlbiBwcmVzc2luZyBhLiBQbGVhc2Ugd3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIG1pbmltdW0gdGltZSByZXF1aXJlZCBmb3IgQ2F0aHkgdG8gdHlwZSBhIHN0cmluZyBzIHdoZW4gc2hlIGNvcGllZCBwIHRvIHRoZSBjbGlwYm9hcmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBULCBUICZsZTsgMjUsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBoYXMgZXhhY3RseSBvbmUgbGluZSBjb250YWluaW5nIHR3byBzdHJpbmdzIHMgYW5kIHAgc2VwYXJhdGVkIGJ5IGJsYW5rcy4gQ2F0aHkgaXMgZ29pbmcgdG8gdHlwZSBzIHdpdGggcCBjb3BpZWQgdG8gdGhlIGNsaXBib2FyZC4gVGhlIGxlbmd0aCBvZiBzIGlzIGF0IG1vc3QgMTAwMDAsIGFuZCB0aGUgbGVuZ3RoIG9mIHAgaXMgYXQgbW9zdCAxMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIG1pbmltdW0gdGltZSAoaW4gc2Vjb25kcykgZm9yIENhdGh5IHRvIHR5cGUgcyB3aXRoIHAgY29waWVkIHRvIHRoZSBjbGlwYm9hcmQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Taiwan > Taiwan Online Programming Contest > TOPC 2015 C번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 번역한 사람: vumbumy