問題
http://community.topcoder.com/stat?c=problem_statement&pm=9839&rd=13504
整数の数列が与えられる。
与えられた数列は、ある実数が公差である数列について小数点以下の数を
切り捨てたものになる。
このとき、公差がいくつであるか求める。
解き方
公差について、２分探索を用いればよい。
コード
int n;
class ArithmeticProgression {
public:
int ispossible(double x,int a0,vector<int> seq){
double cur=a0;
FORE(i,0,n){
cur+=x;
if(floor(cur)==seq[i])continue;
if(floor(cur)>seq[i])return 1;
return -1;
}
return 0;
}
double minCommonDifference(int a0, vector<int> seq) {
if(seq.empty())return 0.0;
n=seq.size();
double low=seq[0]-a0,high=low+1.0;
if(low<0)return -1;
FORE(i,0,100){
double mid=(low+high)/2;
if(ispossible(mid,a0,seq)>=0)high=mid;
else low=mid;
}
return ispossible(high,a0,seq)==0 ? high : -1;
}
};
class ArithmeticProgression {
public:
int ispossible(double x,int a0,vector<int> seq){
double cur=a0;
FORE(i,0,n){
cur+=x;
if(floor(cur)==seq[i])continue;
if(floor(cur)>seq[i])return 1;
return -1;
}
return 0;
}
double minCommonDifference(int a0, vector<int> seq) {
if(seq.empty())return 0.0;
n=seq.size();
double low=seq[0]-a0,high=low+1.0;
if(low<0)return -1;
FORE(i,0,100){
double mid=(low+high)/2;
if(ispossible(mid,a0,seq)>=0)high=mid;
else low=mid;
}
return ispossible(high,a0,seq)==0 ? high : -1;
}
};
Share this
Related Posts
SRM 512 DIV1 Easy - MysteriousRestaurant
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11295&rd=14537
解き方
何日目まで訪れることができるかを固定すること- SRM 445 DIV1 Easy - TheNewHouseDivOne
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10512&rd=13899
解き方
元となる点はすべて座標上の点なので、
すべて
- SRM 394 DIV1 Easy - RoughStrings
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8594&rd=11128
解き方
文字を消す回数0〜ｎ回までそれぞれについて、
- SRM 539 DIV1 Easy - Over9000Rocks
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731
解き方
９０００以上となる数をすべて保存しては間に合