Person in Charge

• 035966_L3

Attention

This problem requires file I/O (pairs.in / pairs.out).

Problem Background

Sleeping Allegator is the steward of a sleeper carriage. The carriage contains a number of beds, each having both an upper and a lower bunk (i.e., each bed accommodates two passengers). One day, while the train is fully loaded, the carriage suddenly loses power!

The passengers immediately become furious and demand that Sleeping Allegator resolve the issue by relocating them to another carriage. Meanwhile, some passengers seize the opportunity to complain that their bunk-mates snore loudly, making it impossible for them to sleep.

Problem Description

Sleeping Allegator summarizes the task as follows:

• There are $n$ beds in the carriage, each with an upper and a lower bunk.
• Every bunk is occupied by exactly one passenger. Some passengers snore (denoted by Z) while others do not (denoted by X).
• The passengers want both bunks of the same bed to have passengers of identical type (both X or both Z).
• Sleeping Allegator may perform the following operations, each costing 1 unit of energy (only one operation can be chosen per step):
  • Swap two adjacent passengers—this can be two upper-bunk passengers from adjacent beds, two lower-bunk passengers from adjacent beds, or the upper and lower passengers of the same bed.
  • Remove a bed only when its upper and lower bunks already satisfy the passengers’ requirement (i.e., both bunks hold the same character).
• The goal is to remove all beds (guaranteed to be possible) while minimizing the total energy spent.

Input Format

The first line contains a single positive integer $n$.

Each of the next $n$ lines contains $2$ characters, representing the upper and lower bunks of a bed.

Output Format

Output a single positive integer: the minimum energy required.

Samples

3
XZ
ZZ
ZX

4

18
XX
XX
XX
XX
XZ
ZX
XZ
ZZ
XZ
XZ
ZZ
XZ
ZX
XZ
XX
XX
XX
XX

24

Explanation for Sample 1

One optimal sequence of moves is:

1. Remove bed $2$ (ZZ already matches) — $1$ energy.
2. Swap the upper (or lower) passengers of the remaining two beds to make them match — $1$ energy.
3. Remove each of the two remaining beds — $2$ energy.

Total energy spent: $4$.

Data Range

For $100\%$ of the data: $1 \le n \le 10^5$ and the counts of both X and Z are even (guaranteeing a solution exists).

Official Solution

link