oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

ramar Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

ramar.html

Mumble, along with his Adele penguin friends, Ramon, Raul and Nestor, were joking around one day when Raul suddenly burst out laughing.

“Hey, Ramon, I can turn your name into a palindrome. Like this. Ramar. Ramar. Rrramarrrrrr.” he chuckled, rolling his r's like only Adele penguins can.

“Oh yeah? Yours is even worse, isn't it? Raar. Raar. Rrrraarrrrrrrr.”

Mumble, being the very very pensive penguin, decided to ignore all that pointless banter and instead concentrate on one of the most important questions in the universe: how many characters does he have to change to make a word a palindrome? Or, even more important, how many characters would he have to change to make a length n word a concatenation of at most k palindromes?

“You two are ridiculous. Maybe all of us are ridiculous. How about Ramonraulnestor? Rar-onrauluarno-r. Look, I did it by changing only 5 characters! Oh no, now I'm ridiculous too. Bwahahahaha!” mused Nestor.

Random interjections by his hyperactive friends are making it really difficult for Mumble to concentrate on the palindrome problem. It's imperative that he solves it as fast as he can, otherwise all his friends and family will run out of fish and starve to death. Help Mumble solve this conundrum. Given a length n string, output the minimum number of characters he would have to change to transform the string into a concatenation of at most k palindromes.

Input

The first line contains n and k.

The second line contains the string in question, containing only lowercase alphabets from a to z.

Output

Output a single integer on a line representing the minimum number of character changes needed to transform the string into a concatenation of k palindromes.

Limits

1 ≤ k ≤ n.

For 25% of the test cases, 1 ≤ n ≤ 10.

For 50% of the test cases, 1 ≤ n ≤ 100.

For 100% of the test cases, 1 ≤ n ≤ 500.

Sample Input 1

5 1
ramon

Sample Output 1

2

Sample Input 2

15 3
ramonraulnestor

Sample Output 2

5

Tags

Dynamic Programming, RI NOI Sel Test 2012

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2021s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o ramar -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.