ITP1_7_B: How many ways? - sinapusu2002 @ ウィキ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。

３変数に見えるが２変数が決まれば残りは自動的に決まるので自由度は２．
すると下記コードのように計算量ＢｉｇＯ（10000）に見える。

#include <iostream>
#include <stdio.h>
using namespace std;
 
int main() {
   while(1){
       int n,x;
       scanf("%d %d",&n,&x);
       if(n==0&&x==0)break;
       int ans=0;
       for(int i=1;i*3+3<=x&&i+2<=n;i++){
           for(int j=i+1;i+j*2+1<=x;j++){
               int k=x-i-j;
               if(j<k&&k<=n){
                   ans++;
               }
           }
            
       }
       printf("%d\n",ans);
   }
   return 0;
}

しかし１変数が決まれば残りの自由度は１．
単純な足し算なのでもっと計算量を削れる。
計算量は最悪でもＢｉｇＯ（33）となる。

#include <iostream>
#include <stdio.h>
using namespace std;
 
int main() {
   while(1){
       int n,x;
       scanf("%d %d",&n,&x);
       if(n==0&&x==0)break;
       int ans=0;
       for(int i=1;i*3+3<=x&&i+2<=n;i++){
       	if(i+n-1+n<x)continue;
           int d=i+1;
           int u=x-i-d;
           ans+=(u-d+1)/2;
           if(u>=n)ans-=(u-n);
       }
       printf("%d\n",ans);
   }
   return 0;
}