Division 1 第一题
Problem Statement
You are watching a soccer match, and you wonder what the probability is that at least one of the two teams will score a prime number of goals. The game lasts 90 minutes, and to simplify the analysis, we will split the match into five-minute intervals. The first interval is the first five minutes, the second interval is the next five minutes, and so on. During each interval, there is a skillOfTeamA percent probability that team A will score a goal, and a skillOfTeamB percent probability that teamB will score a goal. Assume that each team will score at most one goal within each interval. Return the probability that at least one team will have a prime number as its final score.
Definition
Class: PrimeSoccer
Method: getProbability
Parameters: int, int
Returns: double
Method signature: double getProbability(int skillOfTeamA, int skillOfTeamB)
(be sure your method is public)
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
- A prime number is a number that has exactly two divisors, 1 and itself. Note that 0 and 1 are not prime.
Constraints
- skillOfTeamA will be between 0 and 100, inclusive.
- skillOfTeamB will be between 0 and 100, inclusive.
Examples
0)
50
50
Returns: 0.5265618908306351
1)
100
100
Returns: 0.0
Both teams will score a goal in each interval, so the final result will be 18 to 18.
2)
12
89
Returns: 0.6772047168840167
class PrimeSoccer
{
#include <math.h>
long calTotal(int base, int m)
{
long total = 1;
int n = base - m < m ? base-m : m;
int j;
for(j=base+ 1 - n; j<=base;j++)
total *= j;
for( j = 1; j<=n; j++)
total /= j;
return total;
}
double getProbability(int skillOfTeamA, int skillOfTeamB)
{
int primes[] = {2,3,5,7,11,13,17};
int primelength = sizeof( primes ) / sizeof( int );
double sitaA= (double)skillOfTeamA / 100;
double sitaB= (double)skillOfTeamB / 100;
double freA = 0,freB = 0;
int i;
for(i=0; i<primelength; i++)
{
long total = calTotal(18,primes[i]);
freA += (double)total * pow( sitaA,primes[i] ) * pow(1-sitaA,18-primes[i]);
}
for(i=0; i<primelength; i++)
{
long total = calTotal(18,primes[i]);
freB += (double)total * pow( sitaB,primes[i] ) * pow(1-sitaB,18-primes[i]);
}
return 1-(1-freA)*(1-freB);
}
};
第二题
Problem Statement
Several travelers are standing at the entrance of a dark cave. The travelers must all pass through the cave and stand together at the exit. Unfortunately, a variety of circumstances can make it impossible for them to all pass through the cave together at the same time. Therefore, they may have to take turns going through the cave in smaller groups. There is only one map though, and it is impossible to navigate the cave without it, so whenever a group of travelers is inside the cave, one member of that group must be holding the map.
When a group of travelers walks through the cave, either from the entrance or the exit, they must traverse an old bridge to get to the other side of the cave. The entire group inside the cave must cross the bridge together at the same time. The bridge cannot hold more than bridgeStrength kilograms, or it will collapse. You are given a int[] travelersWeights, where the i-th element is the weight of the i-th traveler in kilograms.
Travelers may walk through the cave alone. Although, when travelers walk through the cave in a group of two or more, each traveler must trust at least one of the other travelers in the group. You are given a String[] trustTable, where the j-th character of the i-th element is 'Y' if traveler i trusts traveler j, and 'N' otherwise. Note that the trust relation is not necessarily symmetric.
Travelers walk at different speeds, but when they go through the cave, they must stick together and walk at the same speed. Therefore, when a group of travelers walks through the cave, they must walk at the speed of the slowest traveler in the group. You are given a int[] travelersTimes, where the i-th element is the amount of time it takes the i-th traveler to walk through the cave in any direction.
Return the minimal total time required for all the travelers to end up together at the exit of the cave. If it is impossible, return -1 instead.
Definition
Class: CavePassage
Method: minimalTime
Parameters: int[], int[], String[], int
Returns: int
Method signature: int minimalTime(int[] travelersWeights, int[] travelersTimes, String[] trustTable, int bridgeStrength)
(be sure your method is public)
Constraints
- travelersWeights will contain between 1 and 13 elements, inclusive.
- Each element of travelersWeights will be between 1 and 1000, inclusive.
- travelersTimes will contain the same number of elements as travelersWeights.
- Each element of travelersTimes will be between 1 and 1000, inclusive.
- trustTable will contain the same number of elements as travelersWeights.
- Each element of trustTable will contain exactly n characters, where n is the number of elements in trustTable.
- Each element of trustTable will contain only uppercase letters 'Y' and 'N'.
- The i-th character of the i-th element of trustTable will always be 'Y'.
- bridgeStrength will be between 1 and 5000, inclusive.
Examples
0)
{ 1, 1, 1 }
{ 2, 3, 4 }
{ "YYY", "YYY", "YYY" }
2
Returns: 9
The travelers can achieve the goal as follows. First, traveler 0 and traveler 2 go through the cave together. It normally takes 2 time units for traveler 0 to go through the cave, and it takes 4 time units for traveler 2. Since they are traveling together in a group, they must walk at the speed of the slower traveler. So, after 4 time units, both travelers are at the exit. Then, traveler 0 takes the map and goes back through the cave to the entrance. This time, it only takes 2 time units because he is alone. Finally, traveler 0 and traveler 1 go through the cave together in 3 time units and all the travelers end up together at the exit. The total time is 4 + 2 + 3 = 9.
1)
{ 1, 1, 1 }
{ 2, 3, 4 }
{ "YYY", "YYY", "NYY" }
2
Returns: 10
Here things become a little bit more complicated, because traveler 2 doesn't trust traveler 0.
2)
{ 1, 1, 1 }
{ 7, 13, 19 }
{ "YYN", "NYY", "YNY" }
3
Returns: 19
3)
{ 43 }
{ 23 }
{ "Y" }
42
Returns: -1
第三题
Problem Statement
You have recently bought a field containing gold and silver, and you want to hire some workers to gather the treasure and build beautiful things with it. The field is divided into square cells of equal size. You are given a String[] field, where the j-th character of the i-th element is the content of the cell at row i, column j. A period ('.') represents grass, an uppercase 'X' represents rocks, and uppercase 'G' and 'S' represent gold and silver, respectively. You have also built special workplace cells for your workers, each denoted by an uppercase 'W'.
Each worker must be assigned exactly one workplace, one gold cell and one silver cell. None of these three cells can be assigned to any of the other workers. Each worker will be transporting gold and silver from his cells to his workspace, and for efficiency reasons, you do not want workers to carry anything for more than K meters. This means every worker's workplace must be at most K meters away from his gold cell and at most K meters away from his silver cell. Distance is measured as follows. From each cell, a worker can only move left, right, up or down to an adjacent cell (if one exists). The distance between two consecutive cells is one meter. Workers are only allowed to walk on grass when moving between their cells.
Return the largest number of workers you can hire while meeting these requirements.
Definition
Class: WorkersOnPlane
Method: howMany
Parameters: String[], int
Returns: int
Method signature: int howMany(String[] field, int K)
(be sure your method is public)
Constraints
- field will contain between 1 and 30 elements, inclusive.
- Each element of field will contain between 1 and 30 characters, inclusive.
- Each element of field will contain the same number of characters.
- Each character in each element of field will be a period ('.'), an uppercase 'X', an uppercase 'G', an uppercase 'S' or an uppercase 'W'.
- K will be between 1 and 1000, inclusive.
Examples
0)
{ "G..X",
"..XS",
"W..." }
5
Returns: 1
1)
{ "GG..",
"....",
"..W.",
"..W.",
"SS.." }
4
Returns: 2
2)
{ "GG..",
"XX..",
"..W.",
"..W.",
"SS.." }
10
Returns: 1
We can hire only one worker, because the gold mine in the top left corner can't be reached from any of the workplaces.
3)
{"G.XXX.S",
"G..WW.S"}
11
Returns: 0
If we hire a worker for the left workplace, he won't be able to reach any of the silver mines. Similarly, if we hire a worker for the right workplace, he won't be able to reach gold mines. So we can't hire anybody.