TopCoder 練習 BuildBridge(SRM 295 Div1 Easy)

BuildBridge(SRM 295 Div1 Easy)

■問題
カードの束がある．束が崩れないようにカードを一枚ずつずらしていって橋を作る．長さがLのカードを使って長さDの橋を作るためには，何枚のカードが必要か．

■解法
L=1の時，n枚のカードを重ねると，最大の全長は，
Total Length(n) = Σ_1≦k≦n1/2k
となるため，Total Length(n)≧Dとなるnを求めれば良い．

view plainprint?

1. public class BuildBridge{  
2.  public int howManyCards(int d, int l){  
3.   double dd=(double)d/l;  
4.   double tot=0;  
5.   for(int i=1;;i++){  
6.    tot+=0.5/i;  
7.    if(tot+1e-9>dd) return i;  
8.   }  
9.  }  
10. }  

public class BuildBridge{
 public int howManyCards(int d, int l){
  double dd=(double)d/l;
  double tot=0;
  for(int i=1;;i++){
   tot+=0.5/i;
   if(tot+1e-9>dd) return i;
  }
 }
}

EPS=1e-9としましたが，もう少し小さい(1e-11位)方が安全だと思いました．