POJ3187

今回も全列挙の練習です。こちらの方は前回のようなめんどくさい入力もなく、ただ問題の通りに処理するだけで済みました。

前回覚えたnext_permutationくんにまた頑張ってもらった。 next_permutationくんって辞書順に並べてくれるんですね〜、便利です。

解答時間は20分です。

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, sum, k;
int m[10] = {1,2,3,4,5,6,7,8,9,10};
int tmp[10];

void solve(){
  do{
    k = n;
    for(int i = 0; i < n; i++)
      tmp[i] = m[i];
    while(k>0){
      for(int i = 0; i < k-1; i++){
        tmp[i] += tmp[i+1];
      }
      k--;
    }
    if(tmp[0] == sum)
      break;
  }while(next_permutation(m, m+n));
}

int main(){
  scanf("%d %d", &n, &sum);
  solve();
  for(int i = 0; i < n - 1; i++){
    printf("%d ", m[i]);
  }
  printf("%d\n",m[n-1]);
  return 0;
}