// original:
// Myth5's solution to Google Code Jam 2013 Round 1A C. Good Luck
// http://w...content-available-to-author-only...o.net/jam/13/name/Myth5
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 12 + 5, maxk = 12 + 5;
int R, N, M, K;
long long p[maxk], jc[maxn];
char a[maxn];
// 問題
// 2からMまでの数字がかかれたカードの中から、等確率でN枚のカードを選ぶ
// 以下のことをK回繰り返す
// - N枚のカードのそれぞれを0.5の確率で取り出したサブセットを作る
// - サブセットに含まれるカードの数字の積を書き出す
// N, Mと数字の積から、N枚のカードの数字が何だったかを当てる
// small large
// R 100 8000
// N 3 12
// M 5 8
// K 7 12
// カードの選び方に関する構造体
// a: カードの選び方 (eg. [2, 2, 2, 3, 3, 4, 4])
// rep: このカードの選び方の確率を計算するときに使う値。(2の枚数)! * ... * (Mの枚数)!で計算される
// 直感的に、同じ数字のカードが多い = repの数が大きい = 確率低い
// P: サブセットの積と、その確率をテーブルで保持
// check(): 観測されたサブセットの積がp[]に格納されている時、Pr( サブセットの積 | カードの選び方 )を計算
struct Sol {
string a;
long long rep;
map<long long, int> P;
double check()
{
double ret = 1;
for (int i = 1; i <= K; ++i) {
map<long long, int>::iterator it = P.find(p[i]);
if (it == P.end())
return 0;
ret *= it->second;
}
return ret / rep;
}
void print(){
cout << "-----" << endl;
cout << "a = " << a << endl;
cout << "rep = " << rep << endl;
cout << "P = " << endl;
for(map<long long, int>::iterator it = P.begin();
it != P.end();
++it){
cout << " key: " << it->first << ", val: " << it->second << endl;
}
cout << "-----" << endl;
}
};
vector<Sol> v;
// すべてのカードの選び方をdfsで求める
void dfs(int i)
{
if (i == N) {
// あるカードの選び方が見つかった
Sol t;
t.a = string(a);
//cout << a << endl;
t.rep = 1;
for (int j = 0, k = -1; j < N; ++j)
if (a[j] != a[j + 1]) {
t.rep *= jc[j - k];
k = j;
}
// すべてのとりうるサブセットをシミュレーション
for (int j = 0; j < (1 << N); ++j) {
long long pro = 1;
for (int k = 0; k < N; ++k)
if (j & (1 << k))
pro *= a[k] - '0';
++t.P[pro];
}
v.push_back(t);
// t.print();
}else
//cout << "i = " << i << endl;
for (char j = i > 0 ? a[i - 1] : '2'; j <= '0' + M; ++j) {
//cout << " j = " << j << endl;
a[i] = j;
dfs(i + 1);
}
}
int main()
{
// freopen("c2.in", "r", stdin);
// freopen("c2.out", "w", stdout);
int t2;
cin >> t2;
for (int t1 = 1; t1 <= t2; ++t1) {
printf("Case #%d:\n", t1);
cin >> R >> N >> M >> K;
jc[0] = 1;
for (int i = 1; i <= N; ++i)
jc[i] = jc[i - 1] * i;
a[N] = '\0';
dfs(0);
while (R--) {
for (int i = 1; i <= K; ++i)
cin >> p[i];
double ret = 0;
int reti = 0;
for (int i = 0; i < v.size(); ++i) {
double t = v[i].check();
if (t > ret) {
ret = t;
reti = i;
}
}
cout << v[reti].a << endl;
}
printf("\n");
}
return 0;
}
Ly8gb3JpZ2luYWw6Ci8vICAgTXl0aDUncyBzb2x1dGlvbiB0byBHb29nbGUgQ29kZSBKYW0gMjAxMyBSb3VuZCAxQSBDLiBHb29kIEx1Y2sKLy8gICBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uby5uZXQvamFtLzEzL25hbWUvTXl0aDUKCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgbWF4biA9IDEyICsgNSwgbWF4ayA9IDEyICsgNTsKCmludCBSLCBOLCBNLCBLOwpsb25nIGxvbmcgcFttYXhrXSwgamNbbWF4bl07CmNoYXIgYVttYXhuXTsKCi8vIOWVj+mhjAovLyAy44GL44KJTeOBvuOBp+OBruaVsOWtl+OBjOOBi+OBi+OCjOOBn+OCq+ODvOODieOBruS4reOBi+OCieOAgeetieeiuueOh+OBp07mnprjga7jgqvjg7zjg4njgpLpgbjjgbYKLy8g5Lul5LiL44Gu44GT44Go44KSS+Wbnue5sOOCiui/lOOBmQovLyAgIC0gTuaemuOBruOCq+ODvOODieOBruOBneOCjOOBnuOCjOOCkjAuNeOBrueiuueOh+OBp+WPluOCiuWHuuOBl+OBn+OCteODluOCu+ODg+ODiOOCkuS9nOOCiwovLyAgIC0g44K144OW44K744OD44OI44Gr5ZCr44G+44KM44KL44Kr44O844OJ44Gu5pWw5a2X44Gu56mN44KS5pu444GN5Ye644GZCi8vIE4sIE3jgajmlbDlrZfjga7nqY3jgYvjgonjgIFO5p6a44Gu44Kr44O844OJ44Gu5pWw5a2X44GM5L2V44Gg44Gj44Gf44GL44KS5b2T44Gm44KLCgovLyAgICAgICAgICAgICAgc21hbGwgIGxhcmdlCi8vICAgICAgICBSICAgICAgMTAwICAgODAwMAovLyAgICAgICAgTiAgICAgICAgMyAgICAgMTIKLy8gICAgICAgIE0gICAgICAgIDUgICAgICA4Ci8vICAgICAgICBLICAgICAgICA3ICAgICAxMgoKCi8vIOOCq+ODvOODieOBrumBuOOBs+aWueOBq+mWouOBmeOCi+ani+mAoOS9kwovLyBhOiDjgqvjg7zjg4njga7pgbjjgbPmlrnjgIAoZWcuIFsyLCAyLCAyLCAzLCAzLCA0LCA0XSkKLy8gcmVwOiDjgZPjga7jgqvjg7zjg4njga7pgbjjgbPmlrnjga7norrnjofjgpLoqIjnrpfjgZnjgovjgajjgY3jgavkvb/jgYblgKTjgIIoMuOBruaemuaVsCkhICogLi4uICogKE3jga7mnprmlbApIeOBp+ioiOeul+OBleOCjOOCiwovLyAgICAg55u05oSf55qE44Gr44CB5ZCM44GY5pWw5a2X44Gu44Kr44O844OJ44GM5aSa44GEID0gcmVw44Gu5pWw44GM5aSn44GN44GEID0g56K6546H5L2O44GECi8vIFA6IOOCteODluOCu+ODg+ODiOOBruepjeOBqOOAgeOBneOBrueiuueOh+OCkuODhuODvOODluODq+OBp+S/neaMgQovLyBjaGVjaygpOiDoprPmuKzjgZXjgozjgZ/jgrXjg5bjgrvjg4Pjg4jjga7nqY3jgYxwW13jgavmoLzntI3jgZXjgozjgabjgYTjgovmmYLjgIFQcigg44K144OW44K744OD44OI44Gu56mNIHwg44Kr44O844OJ44Gu6YG444Gz5pa5ICnjgpLoqIjnrpcKc3RydWN0IFNvbCB7CiAgICBzdHJpbmcgYTsKICAgIGxvbmcgbG9uZyByZXA7CiAgICBtYXA8bG9uZyBsb25nLCBpbnQ+IFA7CiAgICBkb3VibGUgY2hlY2soKQogICAgewogICAgICAgIGRvdWJsZSByZXQgPSAxOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IEs7ICsraSkgewogICAgICAgICAgICBtYXA8bG9uZyBsb25nLCBpbnQ+OjppdGVyYXRvciBpdCA9IFAuZmluZChwW2ldKTsKICAgICAgICAgICAgaWYgKGl0ID09IFAuZW5kKCkpCiAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgcmV0ICo9IGl0LT5zZWNvbmQ7CiAgICAgICAgfQogICAgICAgIHJldHVybiByZXQgLyByZXA7CiAgICB9CgogICAgdm9pZCBwcmludCgpewogICAgICAgIGNvdXQgPDwgIi0tLS0tIiA8PCBlbmRsOwogICAgICAgIGNvdXQgPDwgImEgPSAiIDw8IGEgPDwgZW5kbDsKICAgICAgICBjb3V0IDw8ICJyZXAgPSAiIDw8IHJlcCA8PCBlbmRsOwogICAgICAgIGNvdXQgPDwgIlAgPSAiIDw8IGVuZGw7CiAgICAgICAgZm9yKG1hcDxsb25nIGxvbmcsIGludD46Oml0ZXJhdG9yIGl0ID0gUC5iZWdpbigpOwogICAgICAgICAgICBpdCAhPSBQLmVuZCgpOwogICAgICAgICAgICArK2l0KXsKICAgICAgICAgICAgY291dCA8PCAiICAga2V5OiAiIDw8IGl0LT5maXJzdCA8PCAiLCB2YWw6ICIgPDwgaXQtPnNlY29uZCA8PCBlbmRsOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICItLS0tLSIgPDwgZW5kbDsKICAgIH0KfTsKdmVjdG9yPFNvbD4gdjsKCi8vIOOBmeOBueOBpuOBruOCq+ODvOODieOBrumBuOOBs+aWueOCkmRmc+OBp+axguOCgeOCiwp2b2lkIGRmcyhpbnQgaSkKewogICAgaWYgKGkgPT0gTikgewogICAgICAgIC8vIOOBguOCi+OCq+ODvOODieOBrumBuOOBs+aWueOBjOimi+OBpOOBi+OBo+OBnwogICAgICAgIFNvbCB0OwogICAgICAgIHQuYSA9IHN0cmluZyhhKTsKICAgICAgICAvL2NvdXQgPDwgYSA8PCBlbmRsOwogICAgICAgIHQucmVwID0gMTsKICAgICAgICBmb3IgKGludCBqID0gMCwgayA9IC0xOyBqIDwgTjsgKytqKQogICAgICAgICAgICBpZiAoYVtqXSAhPSBhW2ogKyAxXSkgewogICAgICAgICAgICAgICAgdC5yZXAgKj0gamNbaiAtIGtdOwogICAgICAgICAgICAgICAgayA9IGo7CiAgICAgICAgICAgIH0KCiAgICAgICAgLy8g44GZ44G544Gm44Gu44Go44KK44GG44KL44K144OW44K744OD44OI44KS44K344Of44Ol44Os44O844K344On44OzCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCAoMSA8PCBOKTsgKytqKSB7CiAgICAgICAgICAgIGxvbmcgbG9uZyBwcm8gPSAxOwogICAgICAgICAgICBmb3IgKGludCBrID0gMDsgayA8IE47ICsraykKICAgICAgICAgICAgICAgIGlmIChqICYgKDEgPDwgaykpCiAgICAgICAgICAgICAgICAgICAgcHJvICo9IGFba10gLSAnMCc7CiAgICAgICAgICAgICsrdC5QW3Byb107CiAgICAgICAgfQogICAgICAgIHYucHVzaF9iYWNrKHQpOwoKICAgICAgICAKICAgICAgICAvLyB0LnByaW50KCk7CiAgICAgICAgCiAgICB9ZWxzZQogICAgICAgIC8vY291dCA8PCAiaSA9ICIgPDwgaSA8PCBlbmRsOwogICAgICAgIGZvciAoY2hhciBqID0gaSA+IDAgPyBhW2kgLSAxXSA6ICcyJzsgaiA8PSAnMCcgKyBNOyArK2opIHsKICAgICAgICAgICAgLy9jb3V0IDw8ICIgIGogPSAiIDw8IGogPDwgZW5kbDsKICAgICAgICAgICAgYVtpXSA9IGo7CiAgICAgICAgICAgIGRmcyhpICsgMSk7CiAgICAgICAgfQp9CgppbnQgbWFpbigpCnsKICAgIC8vIGZyZW9wZW4oImMyLmluIiwgInIiLCBzdGRpbik7CiAgICAvLyBmcmVvcGVuKCJjMi5vdXQiLCAidyIsIHN0ZG91dCk7CgogICAgaW50IHQyOwogICAgY2luID4+IHQyOwogICAgZm9yIChpbnQgdDEgPSAxOyB0MSA8PSB0MjsgKyt0MSkgewogICAgICAgIHByaW50ZigiQ2FzZSAjJWQ6XG4iLCB0MSk7CiAgICAgICAgY2luID4+IFIgPj4gTiA+PiBNID4+IEs7CiAgICAgICAgamNbMF0gPSAxOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47ICsraSkKICAgICAgICAgICAgamNbaV0gPSBqY1tpIC0gMV0gKiBpOwogICAgICAgIGFbTl0gPSAnXDAnOwogICAgICAgIGRmcygwKTsKICAgICAgICB3aGlsZSAoUi0tKSB7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IEs7ICsraSkKICAgICAgICAgICAgICAgIGNpbiA+PiBwW2ldOwogICAgICAgICAgICBkb3VibGUgcmV0ID0gMDsKICAgICAgICAgICAgaW50IHJldGkgPSAwOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHYuc2l6ZSgpOyArK2kpIHsKICAgICAgICAgICAgICAgIGRvdWJsZSB0ID0gdltpXS5jaGVjaygpOwogICAgICAgICAgICAgICAgaWYgKHQgPiByZXQpIHsKICAgICAgICAgICAgICAgICAgICByZXQgPSB0OwogICAgICAgICAgICAgICAgICAgIHJldGkgPSBpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGNvdXQgPDwgdltyZXRpXS5hIDw8IGVuZGw7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0K