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)の判定法があるはず。