HLAMPS - Lampice
LAMPICE
2*N light bulbs are arranged in two rows and N columns. Each light bulb can be either off or on, and
all lights are initially off.
We want to turn some of them on so that they form a beautiful pattern. In one step we can change
the state of a sequence of (one or more) consecutive light bulbs in the same row or column.
Given the desired pattern, write a program that finds the minimum number of steps required to form
the pattern.
The following figure illustrates the seven steps needed to obtain the pattern given in the third example:
|
0 00000000000000000000 00000000000000000000 |
1 11100000000000000000 00000000000000000000 |
2 11100010000000000000 00000010000000000000 |
3 11100010000000000000 01111101100000000000 |
|
4 11101101111000000000 01111101100000000000 |
5 11101101111000111110 01111101100000000000 |
6 11101101111000101110 01111101100000010000 |
7 11101101111000101010 01111101100000010100 |
input data
The first line of input contains an integer N, 1 ≤ N ≤ 10,000, the number of columns.
Each of the following two lines contains a sequence of N characters representing the desired final
pattern.
Character '1' indicates a light bulb that should be on in the final state, while the character '0' indicates a
light bulb that should be off.
output data
The first and only line of output should contain a single integer – the minimum number of steps
required.
examples
input
3
100
000
output
1
input
5
11011
11011
output
3
input
20
11101101111000101010
01111101100000010100
output
7
| Added by: | DVH |
| Date: | 2013-12-12 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Croatian Regional Competition in Informatics 2006 |
RSS