138 - Street Numbers

問題概要

道に沿って建っている家には1から番号がついている。このうち、ある家から左に行っても右に行っても、通り過ぎる家の番号の和が等しいような、家の数とその家の位置を小さいほうから10個求めよう。

コード

#include<iostream>
#include<cmath>
const long double eps = 1.0e-22;
using namespace std;
int main(){
  int cnt=0;
  for(long long int s = 2; s; ++s){
    long double t = ( sqrt(1+8*s*s) - 1 ) / 2.0;
    if( t - floor(t) < eps ){
      printf("%10lld%10lld\n", s, (long long int)(t));
      ++cnt;
      if(cnt==10)break;
    }
  }
  return 0;
}

等差数列の和から、家の数と家の位置との関係式を求めて、全探索。