問題は Partitioning for fun and profit.

雰囲気.

入力は自然数 m, n, k.

m を n 個 の昇順な自然数に分割する分割を考える.分割の間に辞書式順序を入れたときの k 番目の分割を求める.

例えば,m = 5, n = 3, k = 1 なら,求める分割は [1, 1, 3].

詳細は以下で.

http://icpcres.ecs.baylor.edu/onlinejudge/external/105/10581.html

http://acm.pku.edu.cn/JudgeOnline/problem?id=2522

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1522

題名のとおり.意味が分からない.せめてエラーメッセージをくれ.

単純なDP.別にトッリキーなことは何もしていないのだが…

#include <iostream>
using namespace std;
const int M = 230, N = 12;
int ***f;
void g(int l, int m, int n, int k) {
if (!n) return;
int i = l, s = ;
while (k > s + f[n-1][i][m-i]) {
s += f[n-1][i][m-i];
++i;
}
cout << i << endl;
g(i, m-i, n-1, k-s);
}
int main() {
f = new int **[N];
for (int i = ; i < N; ++i) {
f[i] = new int *[M];
for (int j = ; j < M; ++j)
f[i][j] = new int[M];
}
for (int l = ; l < M; ++l)
f[][l][] = 1;
for (int n = 1; n < N; ++n)
for (int m = ; m < M; ++m)
for (int l = 1; l < M; ++l)
for (int j = l; j <= m / n; ++j)
f[n][l][m] += f[n-1][j][m-j];
int c;
cin >> c;
for (int i = ; i < c; ++i) {
int m, n, k;
cin >> m >> n >> k;
g(1, m, n, k);
}
}

追記

UVaではAccepted,PKUでは Wrong Answerになった.どちらを信じろと?

#include <iostream>
using namespace std;
int main() {
const int M = 221, N = 11;
int **f  = new int*[N];
for (int i = ; i < N; ++i)
f[i] = new int[M];
f[][] = 1;
for (int n = 1; n < N; ++n)
for (int m = ; m < M; ++m)
for (int l = ; n * l <= m - 1; ++l)
f[n][m] += f[n - 1][m - 1 - n * l];
int c;
cin >> c;
for (int i = ; i < c; ++i) {
int m, n, k;
cin >> m >> n >> k;
int j, l = ;
while (n > ) {
for (j = ; k - f[n - 1][m - 1 - n * j] > ; ++j)
k -= f[n - 1][m - 1 - n * j];
cout << l+j+1 << endl;
m -= 1 + n * j, n--, l += j;
}
}
}