HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50488 - Connecting Wires

Guest
• Review clarifications (2)

Section problems

• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50687 - Pascal Triangle - 2
• 50689 - The biggest building block
• 50686 - The Container
• 50682 - Hotel Durres
• 50930 - Tom and Jerry
• 50526 - Gold Market
• 50488 - Connecting Wires
• 50681 - Center of a Series
• 50561 - Lucky tickets
• 50598 - Minimum Sum
• 50601 - Increasing sequence
• 50613 - Zapakovka
• 50680 - Triangle
• 50683 - Parking Buses
• 50685 - Guest Room Usage

Feedback

If you notice incorrect translations in Contester, please let author know.

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


Для отправки решений необходимо выполнить вход.

www.contester.ru