BANDW - Black and White

no tags 

Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011-problems.pdf

The famous game Black and White is a solitaire which is played using a set of identical chips. Each chip has two faces with different colors. Surprisingly enough, those colors are black and white.

The game starts by placing N chips forming a single line. There exists an objective pattern which is a given sequence of N colors black or white. In a single move, the player can choose a group of consecutive chips and invert their color, in other words, for each chip in the group, the color which was facing up, is facing down and the one which was facing down is facing up. The game finishes when the facing up colors of the chips are equal to the objective pattern.

Barby has just discovered this game and soon she realized that you can always won by inverting each chip individually if needed. To make this game more challenging to her, she wanted to win in the least possible number of moves. Note that Barby just cares about how many moves she makes, and it doesn't matter how many chips are inverted in each move. To know how well is Barby playing, she asked you to make a program that given the chip's initial position and the objective pattern, shows the least possible number of moves to win the game. Are you going to say no?

Input

The input contains several test cases. Each test case is described in a single line that contains two non-empty words S and T of equal size and at most 500 letters each. S indicates the chip's initial position while T represents the objective pattern. Both words only contain uppercase letters "B" and "N", representing respectively White and Black. The last line of the input contains two asterisks separated by a single space and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the least possible number of moves such that you can change the chip's which are initially positioned as described in S to form the pattern given by T.

Example

Input:

BBNBBNBBBB NNNNNBBNNB
BNBNB NBNBN
BNBN NBNB
B B
* *

Output:

3
1
1
0

hide comments
up79: 2017-06-06 08:24:41

piece of cake :P

saurav52: 2016-10-20 07:00:31

keep the array size greater than 500

hamjosh1: 2016-09-28 16:30:35

simple question still cost me wa's :'( :D but enjoyed

Last edit: 2016-09-28 16:30:49
kira28: 2016-09-09 22:24:16

any other trickiest test case..plzz
working for all trickiest test case found in the comment, still WA :(

karthik1997: 2016-06-12 14:05:21

Just the total number of consecutive non matching segments .. :p
For ex : 1 BBNBBNBBBB
2 NNNNNBBNNB

We go from 0 th index of both strings and move till end


1 BB
2 NN -> 1 non matching

1 N
2 N ->matching

1 BBN
2 NNB -> non matching =2 till now

1 B
2 B -> matching

1 BB
2 NN - non matching =3 till now

1 B
2 B ->matching

So total =3 tilll the end to make it look similar .... :p

This is for those who didnt read the que clearly and carefully and thought it to be a 2 BIT dp :Pp

Last edit: 2016-06-12 14:06:57
akshayvenkat: 2016-06-03 12:12:01

great question! Some test cases which helped -

NBBN NBNB o/p=1
NNBB BBBB o/p=1
BNBBB BBNBB o/p=1

just_code21: 2015-09-22 18:27:12

cakewalk...

Addy: 2015-08-24 15:11:38

Keep array size greater than 500 to avoid SIGSEV. Cost me one WA!

prakash_reddy: 2015-08-23 20:31:11

easy one..... :)

rsd_unleashed: 2015-05-19 10:18:17

Nice one :)


Added by:Pablo Ariel Heiber
Date:2011-10-04
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2011