TopCoder SRM 413

Div 2果然是水题.第一次SRM,变黄.
yuhch不好好出题啊...
此文测试插件用 有爱者可以忽略

第一题,纯水.贴TC的标程:

double minTime(int length, int maxAcceleration, int maxVelocity) {
  double t1 = sqrt(length / double(maxAcceleration));
  if(maxAcceleration * t1 > maxVelocity) {
    double t2 = maxVelocity / double(maxAcceleration);
    return (length - maxAcceleration * t2 * t2) / maxVelocity + 2 * t2;
  } else
    return 2 * t1;
}

第二题,我的做法是求解一大堆不等式:
假设给出了a0,a1,a2,...其中a1,a2...分别等于[a1],[a2]...,那么
a1-a0<=d<a1-a0+1
a2-a0<=2*d<a2-a0+1
...
TC给出的代码如下:

double minCommonDifference(int a0, vector  seq) {
  // fraction representing 0/1 (minimum permissible value)
  pair  res(0, 1);
  // find d
  for(int i = 0; i < seq.size(); ++i)
    if(res.first * (i + 1) < (seq[i] - a0) * res.second) {
      res.first = seq[i] - a0;
      res.second = i + 1;
    }
  // check whether a solution is possible
  for(int i = 0; i < seq.size(); ++i)
    if(seq[i] != a0 + (i + 1) * res.first / res.second)
      return -1;
  return res.first / double(res.second);
}

出现问题了...先测试到这里

刚才看了一下,Zoundry瞎改HTML.没办法,以后只能到blog后台来写了...装个增强的WYSIWYG插件去...

update:WLW竟然可以用!没想到啊.
继续写完.

第三题看似范围很大,实际用到的状态并不多,所以开一个map做记忆化搜索就解决问题.继续贴TC的代码:

map  mem;
long long calc(long long n, int p, int q) {
  if(n == 0)
    return 1;
  if(mem.count(n))
    return mem[n];
  mem[n] = calc(n / p, p, q) + calc(n / q, p, q);
  return mem[n];
}

这次题目就这样,很水了...
WLW似乎也把line参数给吞了...泪奔...

关闭了可视化编辑器,希望这次能行...
以后就得这么发代码了...