double getArea(int side, int K)
{
double ans = 0.;int n=side;double r=side;
for(int i=0;i<K;i++){
ans += r*r*(1-acos(-1.)/4.); //正方形面積減去圓面積
r /= pow(2.,0.5);
}
return n*n - ans;
}
500pt
You are given six integers, minx, maxx, miny, maxy, minz and maxz. Return the number of triplets of integers (x,y,z) that satisfy the following three conditions:
- x is between minx and maxx, inclusive.
- y is between miny and maxy, inclusive.
- z is between minz and maxz, inclusive.
- x * y = z
Definition
Class:
ProductTriplet
Method:
countTriplets
Parameters:
int, int, int, int, int, int
Returns:
long long
Method signature:
long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz)
(be sure your method is public)
Constraints
-
maxx will be between 1 and 1,000,000,000, inclusive.
-
maxy will be between 1 and 1,000,000,000, inclusive.
-
maxz will be between 1 and 1,000,000,000, inclusive.
-
minx will be between 1 and maxx, inclusive.
-
miny will be between 1 and maxy, inclusive.
-
minz will be between 1 and maxz, inclusive.
Examples
0)
2
2
3
3
6
6
Returns: 1
2 * 3 = 6.
1)
2
2
3
3
7
7
Returns: 0
2 * 3 is not 7.
2)
6
8
4
5
27
35
Returns: 4
(x,y,z) = (6,5,30), (7,4,28), (7,5,35) and (8,4,32) satisfy all conditions.
3)
1
458
1
458
1
458
Returns: 2877
4)
8176
184561
1348
43168
45814517
957843164
Returns: 2365846085
int maximumSubset(vector <string> in)
{
vector<int> vec(2010,0);
int mx=0;
for(int j=0;j<in.size();j++){
stringstream ss(in[j]);string str1,str;int s;
ss>>str1>>str>>s;double k=-1;
for(int i=0;i<2008;i++){
k+=0.5;
bool tag=false;
if(str=="="){
if(s==k)tag=true;
}
else if(str==">="){
if(k>=s)tag=true;
}
else if(str==">"){
if(k>s)tag=true;
}
else if(str=="<="){
if(k<=s)tag=true;
}
else if(str=="<"){
if(k<s)tag=true;
}
if(tag)vec[i]++;
}
}
for(int i=0;i<2008;i++)if(vec[i]>mx)mx=vec[i];
//for(int i=0;i<2008;i++){
//k+=0.5;
//for(int j=0;j<in.size();j++){
// stringstream ss(in[j]);string str1,str;int s;
// ss>>str1>>str>>s;
// bool tag=false;
// if(str=="="){
// if(s==k)tag=true;
// }
// else if(str==">="){
// if(k>=s)tag=true;
// }
// else if(str==">"){
// if(k>s)tag=true;
// }
// else if(str=="<="){
// if(k<=s)tag=true;
// }
// else if(str=="<"){
// if(k<s)tag=true;
// }
// if(tag)vec[i]++;
//}
//if(vec[i]>mx)mx=vec[i];
//}
return mx;
}
要計算最多能滿足的不等式，其實只需要枚舉所有0到1000的數看看每一個能滿足的最多不等式數量，由于k可以是小數，所以以步長0.5遞增即可
1000pt
A new ride is opened in an amusement park. It consists of N landings numbered from 0 to N-1. Some of the landings are connected with pipes. All of the landings are at different heights, so the pipes are all inclined and can only be traversed downwards.
A ride-taker begins his ride at some landing. The pipes are long enough that he cannot see where they lead before entering them. Therefore, at each landing, any descending pipe adjacent to it has an equal probability of being used by a ride-taker who reached this landing.
A ride is finished when a ride-taker reaches a landing which has no adjacent descending pipes. There are two types of such landings: exits and crocodile ponds. If the ride-taker reaches the exit landing, his ride is over and he safely returns home. If one reaches the crocodile pond, his trip is also over, but he never returns home.
You're given a vector <string> landings describing the ride. Element i of landings describes the i-th landing. If the landing is an exit, the i-th character of landings[i] will be 'E' and the rest of the characters will be '0's (zeroes). If it is a crocodile pond, the i-th character will be 'P' and the rest will be '0's. If the landing has at least one adjacent descending pipe, the j-th character of landings[i] will be '1' (one) if a pipe descends from the i-th landing to the j-th, and '0' (zero) otherwise.
A ride-taker began his ride at a randomly chosen landing, used a total of K pipes throughout his descent and safely returned home afterwards. Each of the landings has the same probability of being chosen as the initial landing of the ride. Compute the probability that he started the ride at landingstartLanding.
Definition
Class:
ParkAmusement
Method:
getProbability
Parameters:
vector <string>, int, int
Returns:
double
Method signature:
double getProbability(vector <string> landings, int startLanding, int K)
(be sure your method is public)
Notes
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
landings will contain exactly N elements, where N is between 2 and 50, inclusive.
-
Each element of landings will contain exactly N characters.
-
Each character in landings will be '0' (zero), '1' (one), 'E', or 'P'.
-
If the i-th element of landings contains an 'E', it will contain only one 'E' as its i-th character, and all other characters in that element will be '0'.
-
If the i-th element of landings contains a 'P', it will contain only one 'P' as its i-th character, and all other characters in that element will be '0'.
-
If the i-th element of landings doesn't contain an 'E' or a 'P', it will contain at least one '1' character. The i-th character of such element will always be '0'.
-
K will be between 1 and N-1, inclusive.
-
startLanding will be between 0 and N-1, inclusive.
-
There will be no cycles in landings, i.e. it's never possible to return to the same landing after descending through several pipes.
-
There will be at least one landing from which it is possible to reach an exit using exactly K pipes.
Examples
0)
{"E000",
"1000",
"1000",
"1000"}1
1
Returns: 0.3333333333333333
The ride contains 4 landings, one of which is an exit. Each of the other landings has a single pipe descending to the exit landing. Therefore, each of them could be the starting landing with equal probability of 1/3.
1)
{"E000",
"1000",
"1001",
"000P"}1
1
Returns: 0.6666666666666666
This time, there is an exit landing and a crocodile pond. Of the other two landings, the first has a descending pipe only to the exit, while the second is connected both to the exit and to the pond. So, the probability of reaching an exit starting from landing 2 is lower and the chances of ground 1 being the start of the journey increase.
2)
{"01000100",
"00111000",
"00001010",
"000E0000",
"0000E000",
"00000P00",
"000000P0",
"01000000"}1
2
Returns: 0.14285714285714288
Analyzing the graph above, we can see that landings 0, 1 and 7 could be the starting landings. One can reach an exit from landing 0 using 2 pipes with probability 2/6, from landing 1 with probability 1/6 and from landing 7 with probability 2/3. Therefore, the probability that the ride-taker began from landing 1 is equal to (1/6)/(2/3+2/6+1/6)=1/7.
3)
{"0100",
"0010",
"0001",
"000E"}0
2
Returns: 0.0
Obviously, the only way to get to the exit landing using 2 pipes is from ground 1. Therefore there is no chance that landing 0 was the initial ground.
4)
{"E00",
"0E0",
"010"}0
1
Returns: 0.0
Note that some sections of the ride might be disconnected.
#define REP(i, n) for (int i = 0; i < (n); ++i)
double dp[55][55];
vector<string> A ; int N;
int mp[55];
double cacl(int now,int steps){
if(dp[now][steps]!=-1)return dp[now][steps];
double& t = dp[now][steps];
t=0.;int cnt=0;
REP(i,N){
if(A[now][i]=='1'){
cnt++;t+=cacl(i,steps-1);
}
}
t /= cnt;
return t;
}
class ParkAmusement
{
public:
double getProbability(vector <string> land, int start, int K)
{
A=land; N=land.size();
REP(i,N+1)REP(j,N+1)dp[i][j]=-1;
memset(mp,0,sizeof(mp));// 0
REP(i,N)
REP(j,N){
if(A[i][j]=='E'){
mp[i]=1;
REP(k,N+1)dp[i][k]=0.;
dp[i][0]=1.;
}
else if(A[i][j]=='P')
{
mp[i]=2;
REP(k,N+1)dp[i][k]=0.;
}
}
for(int i=0;i<N;i++)
cacl(i,K);
double ans=0.;
REP(i,N)ans+=dp[i][K];
return dp[start][K]/ans;
}
要求從某個出發安全完成的概率，應該等于從這里出發安全完成的概率比上從各個點出發安全完成概率和。因此要求從每一個點出發安全到達的概率。由于計算中可能出現重復計算，因此使用備忘錄memo[i][j] 計算從i出發經過j步驟安全到達的概率，而此點概率即為此點到其各個鄰接點的安全概率和除以鄰接點個數，所以很簡單，一遍就ac了，可惜晚上沒想明白~