Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question adapted by Ibrahim Mesecan.
Connecting Wires
On random positions, there are n white
dots and n black dots, equally
spaced, in a line. You want to connect each white
dot with some one black dot, with a minimum total
length of "wire".
Total wire length above is 1 + 1 + 1 + 5 = 8.
Question:
Write a program that reads a number n.
And then, it reads (n) strings ("Black" or "White").
Your program, in the end, must calculate
and show the minimum length of the wire needed.
Input specification
The first line contains an integer (n) where
1 ≤ n ≤ 20000 and represents
the number of "Black" and "White" dots. Then, in the
following n lines, you will be given n strings.
Output specification
A single integer which shows the total minimum length of wire
that is needed to connect all Black and White dots.
Sample Input I
4
Black
Black
White
Black
White
White
White
Black
|
Sample Input II
4
Black
Black
White
Black
White
Black
White
White
|
Sample Output I
8
|
Sample Output II
10
|
Для отправки решений необходимо выполнить вход.
|