Walking

AtCoder

IDarc172_f

Time2000ms

Memory256MB

Difficulty—

The Kingdom of AtCoder has $2N$ intersections labeled with numbers from $1$ to $2N$. Additionally, there are three types of **one-way** roads in the kingdom: * **Type A:** For each $2 \leq i \leq N$, there is a road from intersection $2i-3$ to intersection $2i-1$. * **Type B:** For each $2 \leq i \leq N$, there is a road from intersection $2i-2$ to intersection $2i$. * **Type C:** For each $1 \leq i \leq N$, there is a road connecting intersection $2i-1$ and intersection $2i$ with direction $s_i$. Here, $s_i$ is `X` or `Y`, where direction `X` means the road goes from intersection $2i-1$ to intersection $2i$, and direction `Y` means it goes from intersection $2i$ to intersection $2i-1$. Takahashi wants to **walk** several times so that for each $1 \leq i \leq N$, the direction of Type-C road connecting intersections $2i-1$ and $2i$ will be $t_i$. > **What is a walk?** > Start at any intersection and repeat the following action zero or more times: > > * If it is possible to proceed to a Type-C road from the current intersection, walk along the Type-C road to the next intersection. > * Otherwise, if it is possible to proceed to a Type-A or B road from the current intersection, walk along that road to the next intersection. > > Then, reverse the directions of all Type-C roads that were passed. Calculate the minimum number of walks needed to achieve the goal and provide one method to achieve the goal in the minimum number of walks. Under the constraints of this problem, it can be proved that the goal can be achieved in a finite number of walks. ## Constraints * $N$ is an integer such that $1 \leq N \leq 4000$. * Each of $s_1, s_2, \dots, s_N$ is `X` or `Y`. * Each of $t_1, t_2, \dots, t_N$ is `X` or `Y`. ## Input The input is given from Standard Input in the following format: $N$ $s_1 s_2 \cdots s_N$ $t_1 t_2 \cdots t_N$ [samples]

Samples

Input #1

5
XYXYX
XXYXX

Output #1

1
2 7

In this sample input, Takahashi will walk as follows:

*   Start at intersection $2$.
*   Since there is no Type-C road to proceed from intersection $2$, walk along the Type-B road to intersection $4$.
*   Since there is a Type-C road to proceed from intersection $4$, walk along the Type-C road to intersection $3$.
*   Since there is no Type-C road to proceed from intersection $3$, walk along the Type-A road to intersection $5$.
*   Since there is a Type-C road to proceed from intersection $5$, walk along the Type-C road to intersection $6$.
*   Since there is no Type-C road to proceed from intersection $6$, walk along the Type-B road to intersection $8$.
*   Since there is a Type-C road to proceed from intersection $8$, walk along the Type-C road to intersection $7$.
*   Finish at intersection $7$.

This walk passes through the following three Type-C roads:

*   The road connecting intersection $3$ and intersection $4$.
*   The road connecting intersection $5$ and intersection $6$.
*   The road connecting intersection $7$ and intersection $8$.

The directions of these roads are reversed, so the directions of the roads connecting intersections $2i-1$ and $2i$ for $i = 1, 2, 3, 4, 5$ are now `X`, `X`, `Y`, `X`, `X`, respectively, achieving the goal.

Input #2

5
XXYYX
XXYYX

Output #2

0

Note that the goal is already achieved at the beginning, so there is no need to walk even once.

Input #3

5
XXXXX
YYYYY

Output #3

Input #4

20
XXXYXYYXXXYXXXXYYXXY
XXYXYYXXYXXYXYXYXYXY

Output #4

Input #5

20
YXYXYXYYYXYYXYYXYXXX
XXXXXYXYYYXYYXXYYYXY

Output #5

API Response (JSON)

{
  "problem": {
    "name": "Walking",
    "description": {
      "content": "The Kingdom of AtCoder has $2N$ intersections labeled with numbers from $1$ to $2N$. Additionally, there are three types of **one-way** roads in the kingdom: *   **Type A:** For each $2 \\leq i \\leq N",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc172_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Kingdom of AtCoder has $2N$ intersections labeled with numbers from $1$ to $2N$. Additionally, there are three types of **one-way** roads in the kingdom:\n\n*   **Type A:** For each $2 \\leq i \\leq N...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments