AutoLoan srm 258 div2 mid

• 2分探索
  • コメントで消しているのは、n買い目の支払い後の残高を明示的に書いた公式。これだと、テストケース0で駄目だった。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class AutoLoan{
public:
  double func(int n, double price, double r, double c){
//     double ret = 1;
//     for(int i = 0; i < n; i++){
//       ret *= (1 + r / 12);
//     }
//     ret *= (price - 12 * c / r);
//     ret += 12 * c / r;
//     return ret;
    double ret = price;
    for(int i = 0; i < n; i++){
      ret = ret * (1 + r / 12) - c;
    }
    return ret;
  }
  double interestRate(double price, double monthlyPayment, int loanTerm){
    double ret1 = 0, ret2 = 100;
    double ret3;
    int cnt = 0;
    while((abs(ret1 - ret2) > 1e-9) || (((ret2 - ret1) / ret1) > 1e-9)){
      ret3 = (ret1 + ret2) / 2;
      //cout << ret1 << "\t" << ret2 << "\t" << ret3 << endl;
      double val = func(loanTerm, price, ret3 / 100, monthlyPayment);
      if(val < 0){
	ret1 = ret3;
      }
      else if(val > 0){
	ret2 = ret3;
      }
      else{
	return ret3;
      }
      cnt++;
    }
    return (ret1 + ret2) / 2;    
  }



};