시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 690 207 172 32.331%

문제

오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다.

하나의 문자를 입력하려면, 버튼을 눌러야 한다. 버튼을 누르면 버튼에 쓰여 있는 문자가 입력되며, 버튼을 누를 때 마다 다음 문자로 바뀌게 된다. 예를 들어, 2를 누르면 A, 2번 누르면 B, 3번 누르면 C이다. 공백을 연속으로 누를 때는 기다릴 필요가 없다.

입력

첫째 줄에 p와 w가 주어진다. (1 ≤ p, w ≤ 1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자인 문자를 연속으로 찍기 위해 기다리는 시간을 의미한다. 그리고 둘째 줄에는 적을 문자열이 주어진다. 단, 이 문자열의 길이는 1000보다 작고, 맨 앞과 맨 뒤에 공백이 들어오는 경우는 없다고 가정하여도 좋다. 문자열은 알파벳 대문자와 띄어쓰기만으로 이루어져 있다.

출력

첫째 줄에 메시지를 적는데 걸리는 시간을 출력한다.

예제 입력 1

2 10
ABBAS SALAM

예제 출력 1

72
W3sicHJvYmxlbV9pZCI6IjIwMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWJhNTRcdWMyZGNcdWM5YzAiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvMjAxMDA3XC9zbXMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6IDE3NHB4OyB3aWR0aDogMTM3cHg7IGZsb2F0OiByaWdodDtcIiBcLz5cdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1NzhcdWI0ZGNcdWQzZjAgXHVjNzkwXHVkMzEwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Yzc5MFx1ZDMxMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNWI0XHViNWE0IFx1YzYwMVx1YzViNCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVjZTU4XHViODI0XHVhY2UwIFx1ZDU2MCBcdWI1NGMsIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIDFcdWJjODhcdWM3NDAgXHViMjA0XHViOTdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjYzBkXHVkNzhjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjljY1x1YzU3ZFx1YzVkMCBBQ1x1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjZTU4XHViODI0IFx1ZDU1Y1x1YjJlNFx1YmE3NCBBXHViOTdjIFx1Y2U1OFx1YWNlMCBcdWIwOWMgXHVkNmM0IFx1Yzc3Y1x1YzgxNSBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZTMwXHViMmU0XHViOWIwIFx1ZDZjNCBDXHViOTdjIFx1Y2U1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHViODI0XHViYTc0LCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWJjODRcdWQyYmNcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHViYTcwLCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjA0XHViOTdjIFx1YjU0YyBcdWI5YzhcdWIyZTQgXHViMmU0XHVjNzRjIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWJjMTRcdWIwMGNcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyXHViOTdjIFx1YjIwNFx1Yjk3NFx1YmE3NCBBLCAyXHViYzg4IFx1YjIwNFx1Yjk3NFx1YmE3NCBCLCAzXHViYzg4IFx1YjIwNFx1Yjk3NFx1YmE3NCBDXHVjNzc0XHViMmU0LiZuYnNwO1x1YWNmNVx1YmMzMVx1Yzc0NCBcdWM1ZjBcdWMxOGRcdWM3M2NcdWI4NWMgXHViMjA0XHViOTdjIFx1YjU0Y1x1YjI5NCBcdWFlMzBcdWIyZTRcdWI5YjQgXHVkNTQ0XHVjNjk0XHVhYzAwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgcFx1YzY0MCB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBwLCB3ICZsZTsgMSwwMDApIHBcdWIyOTQgXHViYzg0XHVkMmJjXHVjNzQ0IFx1ZDU1Y1x1YmM4OCBcdWIyMDRcdWI5NzRcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YWNlMCwgd1x1YjI5NCBBQ1x1YzY0MCBcdWFjMTlcdWM3NDAsIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWM3NzggXHViYjM4XHVjNzkwXHViOTdjIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWNjMGRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWUzMFx1YjJlNFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDFcdWM3NDQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4LCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWNlMCwgXHViOWU4IFx1YzU1ZVx1YWNmYyBcdWI5ZTggXHViNGE0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM1ZWNcdWIzYzQgXHVjODhiXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWI3NDRcdWM1YjRcdWM0ZjBcdWFlMzBcdWI5Y2NcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWM4MDFcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgU01TIHRvIFR5cGUiLCJkZXNjcmlwdGlvbiI6IjxwPlVzaW5nIFNNUyB0b2RheSBpcyBtb3JlIHRoYW4gYSBwbGVhc2luZyBob2JieS4gQXMgdGhlIG51bWJlciBvZiBtZXNzYWdlcyBvbmUgc2VuZHMgdGhyb3VnaCB0aGlzIHNlcnZpY2UgZ3Jvd3MsIHRoZSBuZWVkIHRvIHR5cGUgdGhlbSBmYXN0IGlzIGJldHRlciBmZWx0LiBTb21ldGltZXMsIG9uZSB3b25kZXJzIGhvdyBmYXN0IGEgbWVzc2FnZSBjYW4gYmUgdHlwZWQuIENoYW5naW5nIHNvbWUgd29yZHMgdG8gdGhlaXIgc3lub255bXMsIG1pZ2h0IGhlbHAgdHlwZSB0aGUgd2hvbGUgbWVzc2FnZSBmYXN0ZXIsIGlmIHdlIHdlcmUgYWJsZSB0byBxdWlja2x5IGNhbGN1bGF0ZSB0aGUgdGltZSBuZWVkZWQgZm9yIGEgc3BlY2lmaWMgbWVzc2FnZS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIGZvbGxvd2luZywgd2UgYXNzdW1lIHRoYXQgZWFjaCBtZXNzYWdlIGlzIGEgc3RyaW5nIG9mIGNhcGl0YWwgRW5nbGlzaCBsZXR0ZXJzIGFuZCBzcGFjZSBjaGFyYWN0ZXIuIFRoZSBsZXR0ZXJzICYjMzk7QSYjMzk7IHRocm91Z2ggJiMzOTtaJiMzOTsgYXJlIGFzc2lnbmVkIHRvIGtleXMgJiMzOTsyJiMzOTsgdG8gJiMzOTs5JiMzOTssIGFzIGluIHRoZSBmb2xsb3dpbmcgZmlndXJlLiBUbyB0eXBlIGEgbGV0dGVyLCBvbmUgc2hvdWxkIHByZXNzIGl0cyBrZXkgMSwgMiwgMywgb3IgNCB0aW1lcywgZGVwZW5kaW5nIG9uIHRoZSBwb3NpdGlvbiBvZiB0aGUgbGV0dGVyIGZyb20gbGVmdCB0byByaWdodC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvc21zLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxNzRweDsgd2lkdGg6MTM3cHhcIiBcLz5JZiB0d28gY29uc2VjdXRpdmUgbGV0dGVycyBvZiB0aGUgbWVzc2FnZSBhcmUgbWFwcGVkIHRvIG9uZSBrZXksIG9uZSBzaG91bGQgd2FpdCBmb3IgdGhlIGZpcnN0IGxldHRlciB0byBiZSBmaXhlZCBvbiB0aGUgc2NyZWVuIGFuZCB0aGVuIHVzZSB0aGUga2V5IGFnYWluIHRvIHR5cGUgdGhlIHNlY29uZCBvbmUuIEZvciBpbnN0YW5jZSwgdG8gdHlwZSB0aGUgbGV0dGVyICYjMzk7WCYjMzk7LCBvbmUgc2hvdWxkIHByZXNzICYjMzk7OSYjMzk7IHR3aWNlLiBJZiB0aGUgbmV4dCBsZXR0ZXIgb2YgdGhlIG1lc3NhZ2UgaXMgbm90IG9uIHRoZSBzYW1lIGtleSwgb25lIGNhbiBjb250aW51ZSB0byB0eXBlIHRoZSByZXN0IG9mIHRoZSBtZXNzYWdlLiBPdGhlcndpc2UsIG9uZSBoYXMgdG8gd2FpdCBmb3Igc29tZSB0aW1lLCBzbyB0aGF0IHRoZSB0eXBlZCAmIzM5O1gmIzM5OyBpcyBmaXhlZCwgYW5kIHRoZW4gdGhlIG5leHQgbGV0dGVyICgmIzM5O1cmIzM5OywgJiMzOTtYJiMzOTssICYjMzk7WSYjMzk7LCBvciAmIzM5O1omIzM5OykgY2FuIGJlIHR5cGVkLiBUbyB0eXBlIHdoaXRlc3BhY2UsIHdlIHVzZSB0aGUga2V5ICYjMzk7MSYjMzk7LiBBcyB0aGVyZSBpcyBubyBsZXR0ZXIgbWFwcGVkIHRvIHRoZSBrZXkgJiMzOTsxJiMzOTssIHRoZSB3aGl0ZXNwYWNlIG5lZWRzIG5vIHRpbWUgdG8gYmUgZml4ZWQuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHRpbWUgbmVlZGVkIHRvIHByZXNzIGFueSBrZXksIGFuZCB0aGUgdGltZSBvbmUgc2hvdWxkIHdhaXQgZm9yIGEgbGV0dGVyIHRvIGJlIGZpeGVkLiBZb3VyIHByb2dyYW0gc2hvdWxkIGZpbmQgdGhlIG1pbmltdW0gdGltZSBuZWVkZWQgdG8gdHlwZSBhIG5vbmVtcHR5IHN0cmluZywgZ2l2ZW4gdGhlIGFib3ZlIHJ1bGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgcCBhbmQgdyAoMSAmbGU7IHAsIHcgJmxlOyAxMDAwKSAsIHdoaWNoIHNob3cgdGhlIGFtb3VudCBvZiB0aW1lIGluIG1pbGxpc2Vjb25kcyBmb3IgcHJlc3NpbmcgYSBsZXR0ZXIgYW5kIHdhaXRpbmcgZm9yIGl0IHRvIGJlIGZpeGVkLCByZXNwZWN0aXZlbHkuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgbGVuZ3RoIGF0IG1vc3QgMTAwMCwgY29uc2lzdGluZyBvZiBzcGFjZXMgb3IgY2FwaXRhbCBFbmdsaXNoIGxldHRlcnMuIFRoZXJlIGlzIG5vIGxlYWRpbmcgb3IgdHJhaWxpbmcgc3BhY2VzIGluIGEgbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgc2hvd2luZyB0aGUgdGltZSBuZWVkZWQgdG8gdHlwZSB0aGUgbWVzc2FnZSBpbiBtaWxsaXNlY29uZHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2005 B번

  • 빠진 조건을 찾은 사람: djm03178