AOJ 10017 - How many ways?

O(n^3)だったはず。n>=1000でTLEするはず。

#include<iostream>

int CountCombination(int n, int x){
	int res = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(i+j+k == x
					 && i != j
					 && i != k
					 && j != k){//i,j,kに重複がないようにする
					res++;
				}
			}
		}
	}
	
	//(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)を重複して数えているので6で割る
	return res/6;
}

int main(){
	int n, x;
	while(std::cin >> n >> x, n){
		std::cout << CountCombination(n, x) << std::endl;
	}
	return 0;
}

O(n^2)にした。n=10000ぐらいまでできるはず。

#include<iostream>

//O(n^2)でもできるはず
//i,jを決めてしまえば自然とkも決まる
int CountCombination(int n, int x){
	int res = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int k = x-(i+j);
			if(i != j
				 && i != k
				 && j != k
				 && k > 0
				 && k <= n){
				//i,j,kに重複がないようにする。条件よりkは(0,n]
				res++;
			}
		}
	}
	
	//(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)を重複して数えているので6で割る
	return res/6;
}

int main(){
	int n, x;
	while(std::cin >> n >> x, n){
		std::cout << CountCombination(n, x) << std::endl;
	}
	return 0;
}

きっとO(n)の判定法があるはず。