Jolly Jumpers..~

Problem Statement
     
In the attic of your house you found an M×N board, divided into MN unit squares. Some of the squares are black and the others are white. You decided that you will make a chessboard out of the board by cutting out an 8×8 region and throwing away the rest of the board.
The only problem is that the board is not painted in the alternate black/white pattern you need for the chessboard. Thus after you cut out the 8×8 chessboard, you will have to repaint some of the squares. Of course, you can pick which 8×8 region to cut out.
You are given the current colors of the squares as a vector <string> board. Character c in element r of board is 'W' if the cell at coordinates (r,c) is white, and 'B' if it is black. Your task is to find the minimum number of squares you will need to repaint after cutting out the 8×8 region.
Definition
   
Class:
RepaintTheChessboard
Method:
minimumChanges
Parameters:
vector <string>
Returns:
int
Method signature:
int minimumChanges(vector <string> board)
(be sure your method is public)
   
 
Notes
-
On a correctly colored chessboard each square is either black or white, and no two squares that share a side have the same color. (Note that according to this definition there are two valid colorings: one with a white, the other with a black square in the upper left corner.)
Constraints
-
board will contain between 8 and 50 elements, inclusive.
-
Each element of board will contain between 8 and 50 characters, inclusive.
-
All elements of board will have the same length.
-
Each character in each element of board will be either 'B' or 'W'.
Examples
0)
 
   
{"BWBWBWBW",
 "WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB"}
Returns: 0
This is a perfect chessboard, no repainting (and no cutting) necessary.
1)
 
   
{"WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB",
 "BWBBBWBW",
 "WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB",
 "BWBWBWBW"}
Returns: 1
This is almost a perfect chessboard, except for one square. (Using 0-based indices, the incorrectly colored square is element 3, character 3 of board.)
2)
 
   
{"BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBB",
 "BBBBBBBBBBBBBBBBBBBBBBW"}
Returns: 31
If we take the 8×8 piece in the lower right corner, we will have one white square, and we will only need 31 more.
3)
 
   
{"BBBBBBBBBB",
 "BBWBWBWBWB",
 "BWBWBWBWBB",
 "BBWBWBWBWB",
 "BWBWBWBWBB",
 "BBWBWBWBWB",
 "BWBWBWBWBB",
 "BBWBWBWBWB",
 "BWBWBWBWBB",
 "BBBBBBBBBB"}
Returns: 0
Here we have a perfect chessboard in the middle of the given board.
4)
 
   
{"WBWBWBWB",
 "BWBWBWBW",
 "WBWBWBWB",
 "BWBBBWBW",
 "WBWBWBWB",
 "BWBWBWBW",
 "WBWBWWWB",
 "BWBWBWBW"}
Returns: 2
For this board the minimum number of changes is 2: We need to change one black square into a white one, and one white square into a black one.
5)
 
   
{"BWWBWWBWWBWW",
 "BWWBWBBWWBWW",
 "WBWWBWBBWWBW",
 "BWWBWBBWWBWW",
 "WBWWBWBBWWBW",
 "BWWBWBBWWBWW",
 "WBWWBWBBWWBW",
 "BWWBWBWWWBWW",
 "WBWWBWBBWWBW",
 "BWWBWBBWWBWW",
 "WBWWBWBBWWBW"}
Returns: 15
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
We have a book with N pages, numbered 1 to N. How many times does each digit occur in the page numbers?
You are given an int N. Return a vector <int> with 10 elements, where for all i between 0 and 9, inclusive, the element i will be the number of times digit i occurs when we write down all the numbers between 1 and N, inclusive.
Definition
   
Class:
PageNumbers
Method:
getCounts
Parameters:
int
Returns:
vector <int>
Method signature:
vector <int> getCounts(int N)
(be sure your method is public)
   
 
Notes
-
You may assume that for any valid input each of the output values fits into an int.
Constraints
-
N will be between 1 and 1,000,000,000, inclusive.
Examples
0)
 
   
7
Returns: {0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }
The page numbers in this case are simply 1, 2, 3, 4, 5, 6, and 7.
1)
 
   
11
Returns: {1, 4, 1, 1, 1, 1, 1, 1, 1, 1 }
In comparison to the previous case, we added the pages 8, 9, 10, and 11. Now we have each digit exactly once, except for the digit 1 that occurs four times: once in 1 and 10, and twice in 11.
2)
 
   
19
Returns: {1, 12, 2, 2, 2, 2, 2, 2, 2, 2 }
Digits 2 to 9 now occur twice each, and we have plenty of occurrences of the digit 1.
3)
 
   
999
Returns: {189, 300, 300, 300, 300, 300, 300, 300, 300, 300 }
Due to symmetry, each of the digits 1 to 9 occurs equally many times in the sequence 1,2,...,999.
4)
 
   
543212345
Returns:
{429904664, 541008121, 540917467, 540117067, 533117017, 473117011, 429904664,
 429904664, 429904664, 429904664 }
Watch out for the time limit.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
We have an N-digit digital counter that increments every second. The counter is cyclic: after it reaches 10^N - 1, it starts once again from zero.
Each digit is shown using the standard seven-segment display. The exact forms of all the digits are shown in the ASCII art below.
    +   +---+   +---+   +   +   +---+
    |       |       |   |   |   |
    +   +---+   +---+   +---+   +---+
    |   |           |       |       |
    +   +---+   +---+       +   +---+
 
+---+   +---+   +---+   +---+   +---+
|           |   |   |   |   |   |   |
+---+       +   +---+   +---+   +   +
|   |       |   |   |       |   |   |
+---+       +   +---+       +   +---+
Each line segment that connects two adjacent '+' symbols represents a single lit segment. For example, '1' contains two lit segments, and '9' contains five lit segments.
You are given a string current that contains the current number shown by the counter. The number of characters in current is equal to the number N of displayed digits.
Return the smallest positive number of seconds after which the counter will have the same total number of lit segments as it does now.
Definition
     
Class:
DigitalCounter
Method:
nextEvent
Parameters:
string
Returns:
long long
Method signature:
long long nextEvent(string current)
(be sure your method is public)
   
 
Notes
-
The digits 1, 2, ..., 9, and 0 have 2, 5, 5, 4, 5, 6, 3, 7, 5, and 6 lit segments, respectively.
-
The counter does always show leading zeroes. (See Examples #3 and #5.)
-
As the counter is cyclic, the answer always exists and for any valid input the answer fits into a long long.
Constraints
-
current will contain between 1 and 15 characters, inclusive.
-
Each character in current will be a digit ('0'-'9').
Examples
0)
 
   
"1"
Returns: 10
No other digit has exactly two segments lit, thus the next time there will be two segments lit will be in 10 seconds.
1)
 
   
"3"
Returns: 2
In 2 seconds the display will show "5", and "5" and "3" both have exactly five lit segments.
2)
 
   
"9"
Returns: 3
In 3 seconds, the display will show "2".
3)
 
   
"99"
Returns: 5
The number "99" is shown using 5+5=10 lit segments. In 5 seconds, the display will show "04", with 6+4=10 lit segments again.
4)
 
   
"654371"
Returns: 43
 
5)
 
   
"007"
Returns: 11
Note that the input can have leading zeroes.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.