Problem Statement
 
You are given a int[] f that describes a set of values from a function f. The x-th element (zero-indexed) is the value of f(x). The function is not convex at a particular x value if there exist y and z values such that y < x < z, and the point (x, f(x)) lies strictly above the line between points (y, f(y)) and (z, f(z)) in the Cartesian plane. All x, y, and z values must be between 0 and n-1, inclusive, where n is the number of elements in f. Return the number of places where f is not convex.
Definition
 
Class:
ConvexityIssues
Method:
howMany
Parameters:
int[]
Returns:
int
Method signature:
int howMany(int[] values)
(be sure your method is public)
 

Constraints
-
f will contain between 3 and 50 elements, inclusive.
-
Each element of f will be between -1000 and 1000, inclusive.
Examples
0)

 
{0,1,4,9,16,25}
Returns: 0
The function is convex at all given points.
1)

 
{0,2,2}
Returns: 1
The point (1,2) is not below the line from (0,0) to (2,2).
2)

 
{1, 2, 3, 4, 5, 6, 7, 8}
Returns: 0

3)

 
{-1000, -501, 0, 500, 1000}
Returns: 2

4)

 
{-1000, 1, 1000}
Returns: 1


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.

------------------------------------------------------------------------------------------------------------250分

Problem Statement
 
You are given a grid of characters, where each element describes a row. A solid square is a contiguous n x n section of characters, all of which have the same value. Return the number of solid squares in grid that aren't contained in larger solid squares.
Definition
 
Class:
SquareCounting
Method:
howMany
Parameters:
vector <string>
Returns:
int
Method signature:
int howMany(vector <string> grid)
(be sure your method is public)
 

Constraints
-
grid will contain between 1 and 10 elements, inclusive.
-
Each element of grid will contain between 1 and 10 characters, inclusive.
-
Each element grid will contain the same number of characters.
-
Each character in grid will be an uppercase letter ('A'-'Z').
Examples
0)

 
{"AB",
"CD"}
Returns: 4
Here we have 4 separate 1 x 1 squares.
1)

 
{"AAB",
"AAB",
"BBB"}
Returns: 6
Here we have a 2 x 2 square of 'A's and 5 squares of 'B's (each 1 x 1). Thus we return 6.
2)

 
{"AA",
"AA",
"AA"}
Returns: 2
The two possible 2 x 2 squares are counted.
3)

 
{"AAA",
"AAA",
"AAA"}
Returns: 1
Only the large 3x3 square is countable.
4)

 
{
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA",
"AAAAAAAAAA"
}
Returns: 1

5)

 
{
"AAAAAABBB",
"AAAAAABBB",
"AAAAAABBB",
"AAAAAABBB",
"AAAAAABBB",
"BBBAAAAAA",
"BBBAAAAAA",
"BBBAAAAAA",
"BBBAAAAAA",
"BBBAAAAAA"
}
Returns: 12


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.

------------------------------------------------------------------------------------------------------------250分

Problem Statement
 
During a soccer match, the referee can warn players by showing them red or yellow cards. When a player is shown a red card, he is sent off the field immediately. The first time a player is shown a yellow card, it serves as a warning. The second time he is shown a yellow card in the same match, he is immediately shown a red card as well, and sent off the field. When players are sent off the field, they are out for the remainder of the match. During the last World Cup, a referee forgot that one of the players was already shown a yellow card, and did not send him off after the second one. You are to write a program to prevent such errors.
You will be given a vector <string> info, the i-th element of which represents the i-th card shown during the match. Each element of info will be formatted as "C NN SURNAME" (quotes for clarity only). C is a character 'Y' or 'R', representing a yellow or red card, respectively. NN is a two-digit number representing the minute when the card was shown. SURNAME contains between 2 and 20 uppercase letters and represents the surname of the player who was shown the card. For the purposes of this problem, we assume that surnames are unique for all players. If you find that the referee made at least one error during the match (i.e., he showed a second yellow card to one player but didn't show him a red card at the same minute), return the earliest minute when this happened. If the referee didn't make any errors, return -1. Please note that the referee may occasionally show more than two yellow cards to the same player during a single minute, and this is legal as long as he also shows the red card to that player later in the same minute (see example 6).
Definition
 
Class:
RedCard
Method:
firstError
Parameters:
vector <string>
Returns:
int
Method signature:
int firstError(vector <string> info)
(be sure your method is public)
 

Constraints
-
All elements of info will be in chronological order. In other words, the time represented by the i-th element of info will be greater than or equal to the time represented by the (i-1)-th element.
-
If a player is shown a red card, no later elements of info will contain that player.
-
info will contain between 0 and 50 elements, inclusive.
-
Each element of info will contain between 7 and 25 characters, inclusive.
-
Each element of info will be formatted as "C NN SURNAME".
-
In each element of info C will be either 'Y' or 'R'.
-
In each element of info NN will be a two-digit number between 00 and 90, inclusive.
-
In each element of info SURNAME will contain between 2 and 20 uppercase letters ('A' - 'Z'), inclusive.
Examples
0)

 
{"Y 10 JOHNS", "Y 70 JOHNS", "R 70 JOHNS"}
Returns: -1

1)

 
{"Y 10 JOHNS", "R 70 JOHNS"}
Returns: -1

2)

 
{"Y 10 JOHNS", "Y 10 SMITH", "Y 20 JOHNS", "Y 20 SMITH", "R 20 SMITH", "R 20 JOHNS"}
Returns: -1
Both red cards are shown at the same minute as the second yellow cards, so the referee didn't make any error here.
3)

 
{"Y 10 JOHNS", "Y 15 JOHNS", "Y 70 JOHNS", "R 70 JOHNS"}
Returns: 15

4)

 
{"Y 10 SMITH", "Y 13 WILLIAMS", "Y 70 SMITH", "Y 70 JOHNS",
"R 70 SMITH", "Y 71 JOHNS", "R 71 JOHNS", "R 90 WILLIAMS"}
Returns: -1

5)

 
{
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS",
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS",
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS",
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS",
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 02 JOHNS"
}
Returns: 1
Both Johns and the referee were really active from the very beginning of the game.
6)

 
{
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS",
"Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "Y 01 JOHNS", "R 01 JOHNS"
}
Returns: -1


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.

--------------------------------------------------------------------------------------------------250分

Problem Statement
 
Alex has a lot of contacts in his Hyper Instant Messenger (HIM), and therefore, it takes some time to find the right contact. HIM supports Contact Groups, and each contact can be placed into a group. However, HIM's group support is rather limited. It allows for only one of the following two scenarios: 1) Multiple groups, but every contact belongs to a single group, or 2) All contacts exist only in a global contacts list (and no groups are created).
It takes Alex k seconds to find an entry in any list of k entries. If groups exist, HIM will first show a list of all the groups, and once a group is selected, a list of all contacts within that group will be displayed. If groups do not exist, HIM will simply show a single list containing all the contacts in the global list. For example, if Alex has 5 contacts in the global list, it will take 5 seconds to find any one of them. If Alex splits those contacts into two groups with 2 and 3 users each, it will first take him 2 seconds to find the right group, and then 2 or 3 seconds to find the right contact depending on which group he chooses.
You will be given an int N representing the total number of contacts. Arrange the contacts optimally (either in one global contacts list or in several groups) such that the maximal time needed to find a contact is minimized. Return this time.
Definition
 
Class:
IMGroups
Method:
optimalTime
Parameters:
int
Returns:
int
Method signature:
int optimalTime(int N)
(be sure your method is public)
 

Constraints
-
N will be between 1 and 1000000, inclusive.
Examples
0)

 
5
Returns: 5
The example from the problem statement.
1)

 
6
Returns: 5
Alex can arrange the contacts into 2 groups with 3 contacts each. The total time needed to find any contact will be 2 seconds to find the right group plus 3 seconds to find the right contact within that group.
2)

 
1000
Returns: 64


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.

------------------------------------------------------------------------------250分

Problem Statement
 
You have a card shuffling machine that takes a stack of m cards and reorders them according to the sequence given in shuffled. For example, if the third element of shuffled is 7, then the 7th card of the input will be the third card of the output. You will take the sequence of cards 1, 2, 3, ..., m, and feed it into the shuffling machine n times. Each time (except for the first time), you will feed the resulting sequence from the previous time back into the machine. Return the resulting sequence after the last run of the machine.
Definition
 
Class:
DeckShuffler
Method:
getDeck
Parameters:
int, vector <int>
Returns:
vector <int>
Method signature:
vector <int> getDeck(int n, vector <int> shuffled)
(be sure your method is public)
 

Constraints
-
n will be between 1 and 100, inclusive.
-
Each element of shuffled will be between 1 and m, inclusive, where m is the number of elements in shuffled.
-
shuffled will contain between 1 and 50 elements, inclusive.
-
Each element of shuffled will be distinct.
Examples
0)

 
10
{1,2,3,4}
Returns: {1, 2, 3, 4 }
The machine doesn't actually change any positions so we return {1,2,3,4}.
1)

 
3
{2,1,3,4,5}
Returns: {2, 1, 3, 4, 5 }
The machine swaps the first two cards. Performing this procedure 3 times gives the resulting sequence {2,1,3,4,5}.
2)

 
3
{3,1,2}
Returns: {1, 2, 3 }
The machine cyclically permutes the cards, so shuffling 3 times is like not shuffling at all. We return {1,2,3}.
3)

 
100
{2,1,4,5,3,7,8,9,6,11,12,13,14,10}
Returns: {1, 2, 4, 5, 3, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

4)

 
13
{2,1,4,5,3,7,8,9,6,11,12,13,14,10}
Returns: {2, 1, 4, 5, 3, 7, 8, 9, 6, 13, 14, 10, 11, 12 }

5)

 
1
{3,1,5,2,4}
Returns: {3, 1, 5, 2, 4 }


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.

-------------------------------------------------------------------------------------------250分

Problem Statement
 
You are given a square chessboard, and you must determine the number of ways you can place k bishops on the board so that no two bishops attack each other. Some of the cells on the board are destroyed, and a bishop cannot be placed on a destroyed cell. Two bishops attack each other if they are located on the same diagonal (even if there are destroyed cells between them).
You will be given a vector <string> board which represents the chessboard. The jth character of the ith element of board represents the cell at row i, column j. A '.' denotes an empty cell, and a '#' denotes a destroyed cell. Return the last four digits of the number of ways you can place k bishops on the board so that no two bishops attack each other.
Definition
 
Class:
Bishops
Method:
count
Parameters:
int, vector <string>
Returns:
int
Method signature:
int count(int k, vector <string> board)
(be sure your method is public)
 

Constraints
-
k will be between 0 and 64, inclusive.
-
board will contain between 1 and 8 elements, inclusive.
-
Each element of board will contain exactly n characters, where n is the number of elements in board.
-
Each character of each element of board will be either '.' or '#'.
Examples
0)

 
1
{"."}
Returns: 1

1)

 
1
{
"...",
".##",
"..."}
Returns: 7
There are 7 free cells, and the bishop can be placed in any of those cells.
2)

 
3
{
"...",
"...",
"..."}
Returns: 26

3)

 
7
{
"........",
"......#.",
"........",
".#......",
"........",
".....#..",
"........",
"...#...."}
Returns: 5544

4)

 
4
{
"...",
".#.",
"..."}
Returns: 8
There are two basic possible placements of 4 bishops:
BBB B.B
.#. B#B
.B. ...
and the rotations of these two placements.
5)

 
0
{
"...",
"###",
"..."}
Returns: 1
There is exactly one way of placing 0 bishops.
6)

 
2
{
"....",
"....",
".#..",
"...#"}
Returns: 71


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.

---------------------------------------------------------------------------------------750分

Problem Statement
 
The permanent of a nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] over all permutations p of the set {1, 2, ... , n}.
You will be given a vector <string> matrix, where each element contains a single space delimited list of integers. The jth integer in the ith element represents the value of A[i][j]. Return the int represented by the last four digits of the permanent of the given matrix.
Definition
 
Class:
PermanentComputation
Method:
compute
Parameters:
vector <string>
Returns:
int
Method signature:
int compute(vector <string> matrix)
(be sure your method is public)
 

Constraints
-
matrix will contain between 1 and 16 elements, inclusive.
-
Each element of matrix will contain a list of integers, each separated by exactly one space.
-
Each element of matrix will contain exactly n integers, where n is the number of elements in matrix.
-
Each element will have length between 1 and 50 characters, inclusive.
-
Each element of matrix will contain no leading or trailing spaces.
-
Each integer in matrix will be between 0 and 10000, inclusive, and contain no leading zeroes.
Examples
0)

 
{
"1 1",
"1 1"}
Returns: 2
The permanent is equal to 1*1 + 1*1 = 2.
1)

 
{
"1 2 3",
"4 5 6",
"7 8 9"}
Returns: 450
The permanent is equal to 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*4*8 + 3*5*7 = 450.
2)

 
{
"1 2 3 4",
"2 3 4 5",
"3 4 5 6",
"4 5 6 7"}
Returns: 4276

3)

 
{
"1 1 1",
"2 2 2",
"3 3 3"}
Returns: 36

4)

 
{
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
"1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"}
Returns: 8000


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.

---------------------------------------------------------------------750分

无人来嗅

你不如打包传上来

我名到是报了,就是那天一直在上课,没参加.(其实本来我实力就还不行,所以参不参加也无所谓了,呵呵:)

我那天一直没有课 一个系的嘛 你选的什么方向哦

蝈蝈能解释一下Google CodeJam2006 Qualification Round 吗？

谷歌全球程序挑战赛资格赛环节