TopCoder SRM#676(Div2)(2/3)

maksyuki 发表于 比赛 分类,标签:

250 Problem Statement

Farmer John recently found out about a popular online farming game.There are n types of plants in the game. The types are numbered 0 through n-1. At the beginning of the game, Farmer John is given one seed of each plant type.There is a single plot of land. At any time the plot can only contain at most one plant. Whenever the plot is empty, Farmer John can plant one of the seeds. Once a seed of type i is planted, it takes time[i] seconds until it grows into a fully developed plant. When that happens, Farmer John will harvest the plant and the plot will become empty again. Planting a seed and harvesting a plant happens instanteously.
Farmer John also has budget coins. He can spend these coins to make his plants grow faster. For each i, Farmer John may pay cost[i] coins to reduce time[i] by 1. Farmer John may pay for the same plant multiple times, each time decreasing its growing time by 1. Obviously, the growing time cannot be reduced below 0.
You are given the vector <int>s time and cost with n elements each, and the int budget. Determine and return the minimum amount of time in which Farmer John can grow a single plant of each type.

vector <int>, vector <int>, int
Method signature:
int minTime(vector <int> time, vector <int> cost, int budget)
(be sure your method is public)





550 Problem Statement

Alice and Bob have a rectangular board divided into a grid with r rows and c columns. The grid is described by the vector <string> s. Each character of s represents one cell. There are four types of cells:

'E' denotes an exit. There may be arbitrarily many exits, possibly zero.
'T' means the square contains a single token. Initially there will be exactly one token on the entire board.
'#' denotes an obstacle.
'.' denotes an empty cell.
Alice and Bob will play a game on this board. The game is parameterized by the int k. The token initially has the number k on it. The players will take alternating turns, starting with Alice. A player's turn consists of the following steps:

The player moves the token one square up, down, left, or right. The token cannot go over the edge of the board and it cannot enter a cell with an obstacle.
If this token is on an exit, it disappears from the board.
Otherwise, subtract one from the number on the token. If the number on the token is zero, remove it from the board.
The first player unable to make a move loses the game. (This happens when the token is stuck and also when it already left the board.)

You are given the vector <string> s and the int k Compute the winner of the game, assuming both Alice and Bob play optimally. Return the winner's name: either "Alice" or "Bob". Note that the return value is case-sensitive.

Class: BoardEscapeDiv2
Method: findWinner
Parameters: vector <string>, int
Returns: string
Method signature: string findWinner(vector <string> s, int k)
(be sure your method is public)