Sphere Online Judge

SPOJ Problem Set (classical)

10537. Edit Distance Again

Problem code: EDIT


 

As any experienced programmer must know the famous problem of "Edit Distance", however this
problem is considered an “alternating chain” if you have alternately made case sensitive.
Example:
"AaAaAbB" "B" "a" "aBaCdEf"
Alternating chains are considered in our problem.
We only have one operation that is permitted in exchange for a lower or upper case Latin letter.
Given a string giving the minimum number of changes to be considered an alternating chain.

 

As any experienced programmer must know the famous problem of "Edit Distance", however this

problem is considered an “alternating chain” if you have alternately made case sensitive.

Example:

"AaAaAbB" "B" "a" "aBaCdEf"

Alternating chains are considered in our problem.

We only have one operation that is permitted in exchange for a lower or upper case Latin letter.

Given a string giving the minimum number of changes to be considered an alternating chain.

 

 

Input

 

A string with no spaces line containing only uppercase and lowercase letters, one for each line of

maximum length 10 ^ 3 until end of file

 

Output

 

For each line print the minimum number of changes to the chain is a "chain alternately"

 

Example

Input:
AaAaB
ABaa
a

Output:
0
2
0

Added by:Paulo Costa
Date:2012-02-01
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:PUCP

hide comments
2014-07-17 07:17:06 Mitch Schwartz
@Sahil Dua: '\0'
2014-07-17 05:04:13 Sahil Dua
I had an array of size 1000, got Segmentation fault. Then changed it to 1005, and got AC.

Strange! Any explanations to this?
2014-03-04 15:44:49 Aditya Deepak
in second case given the number of exchanges should be 1 how it is 2 ?
2013-12-22 09:52:32 bad-coder
what would be the size of array,i am
getting segmentation fault
2013-12-17 20:40:36 Code Geass
very easy problem.. :)
AC at first attempt...
@Nishant Raj.. thanks for the hint.. :D
2013-12-16 10:33:15 NISHANT RAJ
TAKE HELP OF BINARY ARRAY.THEN IT WILL WORK FOR ALL CASE.
BINARY ARRAY:-10101110....
SOME THING LIKE THIS
2013-12-14 18:25:13 ABHISHEK004
got tle using gets but acc using scanf..... :/
2013-12-14 13:14:35 Jumpy
be aware of this case :
AAaAaAA
2013-10-27 07:36:34 Somesh Maurya™
feeling like a kid.
a trick test case:-
aaAaAa
answer is 1
2013-10-25 17:25:53 Faizuddarain Syam
very easy,
but i like these kinds of prob..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.