201095: [AtCoder]ARC109 F - 1D Kingdom Builder

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $900$ points

Problem Statement

Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer $i$, Square $i$ and Square $i+1$ are adjacent. Additionally, each square is painted white or black.

A string $s$ of length $n$ consisting of w and b represents the colors of the squares of this board, as follows:

  • For each $i = 1, 2, \dots, n$, Square $i$ is white if the $i$-th character of $s$ is w, and black if that character is b;
  • For each $i \leq 0$, Square $i$ is white;
  • For each $i > n$, Square $i$ is black.

Snuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:

  • (1) Choose a piece of the color of his choice.
  • (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.
    • (2a) If there are such squares, choose one of them and put the piece on it;
    • (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.

The board initially has no piece on it.

You are given a string $t$ of length $n$ consisting of o and _. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square $i$ among Squares $1,..,n$ such that the $i$-th character of $t$ is o. It is guaranteed that $t$ has at least one occurrence of o.

Constraints

  • $1 \leq n \leq 10^5$
  • $|s| = |t| = n$
  • $s$ consists of w and b.
  • $t$ consists of o and _.
  • $t$ has at least one occurrence of o.

Input

Input is given from Standard Input in the following format:

$n$
$s$
$t$

Output

Print the minimum number of pieces Snuke needs to put on the board.


Sample Input 1

3
wbb
o_o

Sample Output 1

2

Let us use W to represent a white square that needs a piece on it, B to represent a black square that needs a piece on it, w to represent a white square that does not need a piece on it, and b to represent a black square that does not need a piece on it.

We have the following board:

...wwwwwwWbBbbbbb...

If we put pieces in the following order, two pieces is enough:

...wwwwwwWbBbbbbb...
         2 1

Note that if we put a piece on the white square first, we will need three or more pieces:

...wwwwwwWbBbbbbb...
         123

Sample Input 2

4
wwww
o__o

Sample Output 2

3

If we put pieces in the following order, three pieces is enough:

...wwwwwWwwWbbbbb...
        1  32

Sample Input 3

9
bbwbwbwbb
_o_o_o_o_

Sample Output 3

5

If we put pieces in the following order, five pieces is enough:

...wwwwwbBwBwBwBbbbbbb...
        12 3 4 5

Sample Input 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_

Sample Output 4

11

Input

题意翻译

有一个无限长的数轴,每个点有个颜色,$\leqslant 0$ 的点为白色,$>n$ 的为黑色,$[1,n]$ 由输入给出。在 $[1,n]$ 内有若干个需要标记的点。一次标记时需先选定一个颜色,如果存在这个颜色的未标记过的点,且存在与之相邻的点被标记过,则从中选择一个标记;否则,随意选择一个这个颜色的没有标记过的点标记。求把要求标记的点全部标记到的最小彪子次数。

加入题单

上一题 下一题 算法标签: