HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50488 - Connecting Wires

Guest
• Review clarifications (2)

Section problems

• 50688 - Epoka Furgon
• 50689 - The biggest building block
• 50686 - The Container
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50682 - Hotel Durres
• 50526 - Gold Market
• 50930 - Tom and Jerry
• 50488 - Connecting Wires
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 50598 - Minimum Sum
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50674 - Collecting Eggs
• 50561 - Lucky tickets

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