SRM347Div2

250

class CarBuyer {
public:
  double lowestCost(vector <string> cars, int f, int dist, int y) {
    double ret = 1e256;

    for(int i=0; i<cars.size(); ++i){
      istringstream iss( cars[i] );
      double pur, tax, eff;
      iss >> pur >> tax    >> eff;
      double cost = f * dist / eff * y + tax * y + pur;
      ret = min( ret, cost );
    }

    return ret;
  }
};

500
何度か誤差死した。

double dist(vector<int> p1, vector<int> v1, vector<int> p2, vector<int> v2, double t)
{
  double ret = 0;
  for(int i=0; i<3; ++i){
    double a = p1[i] + t * v1[i];
    double b = p2[i] + t * v2[i];
    ret += (a - b) * (a - b);
  }
  return sqrt( ret );
}

class Aircraft {
public:  
  string nearMiss(vector <int> p1, vector <int> v1, vector <int> p2, vector <int> v2, int R) {

    double big = 1000000;
    double small = 0;
    double right = 0, left = 0;

    for(int loop = 5000; loop--; ){

      left = (big - small) / 3.0 + small;
      right = (big - small) * 2.0 / 3.0 + small;
      
      double dl = dist(p1, v1, p2, v2, left);
      double dr = dist(p1, v1, p2, v2, right);
      
      if( dr < dl ) small = left;
      else big = right;
      
    }

    double d = dist(p1, v1, p2, v2, left);

    return d <= (double)R + 1e-8 ? "YES" : "NO";
  }
};

1000

const int inf = 1 << 24;

const int N = 50 + 1;
int g[N][N];

const int T = 1 << 12;
int t[T][N];

int rec(int bit, int pos, const vector< pair<int, int> > &v) 
{
  if( bit == 0 )return g[pos][0];
  if( t[bit][pos] != inf )return t[bit][pos];

  int mn = inf;
  for(int i=0; (1 << i) <= bit; ++i){
    if( bit & (1 << i) ){
     
      int cost = 0;
      cost += g[ pos ][ v[i].first ];
      cost += g[ v[i].first ][ v[i].second ];
      cost += rec( bit ^ (1 << i), v[i].second, v );

      mn = min( mn, cost );
    
    }
  }
  
  return t[bit][pos] = mn;
}

class TaxiManager {
public:
  int schedule(vector <string> roads, vector <string> customers) {

    const int size = roads.size();

    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] = roads[i][j] - '0';
        if( g[i][j] == 0 ) g[i][j] = inf;
      }
    }
    for(int i=0; i<size; ++i){
      g[i][i] = 0;
    }

    for(int k=0; k<size; ++k){
      for(int i=0; i<size; ++i){
        for(int j=0; j<size; ++j){
          g[i][j] = min( g[i][j], g[i][k] + g[k][j] );
        }
      }
    }

    vector< pair<int, int> > v;
    for(int i=0; i<customers.size(); ++i){
      istringstream iss( customers[i] );
      pair<int, int> p;
      iss >> p.first >> p.second;
      //--p.first; --p.second;
      v.push_back( p );
    }

    fill( t[0], t[T], inf );

    int mn = inf;
    const int B = (1 << v.size()) - 1;
    
    for(int bit = 0; bit < (1 << v.size()); ++bit){
      mn = min( mn, max(rec(bit, 0, v), rec(B ^ bit, 0, v)) );
    }

    return mn;
  }
};