“午餐饭团”是百度内部参与人数最多的民间组织。同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们增进感情。 但是，随着百度的员工越来越多，各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃，饭团的点菜负责人的压力也越来越大。现在，这个任务就交给“百度之星”了，因为，你将要为所有的百度饭团设计一个自动点菜的算法。 饭团点菜的需求如下： 1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近12元越好。 2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。 3．请谨记，百度饭团在各大餐馆享受8折优惠。 格式 输入格式： 1．输入数据第一行包含三个整数N，M，K（0<N<=16， 0<M<=N， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。 2．紧接着N行，每行的格式如下：菜名（长度不超过20个字符） 价格（原价，整数） 是否荤菜（1表示是，0表示否） 是否辛辣（1表示是，0表示否）； 3．第N+2行是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。 输出格式： 对于每组测试数据，输出数据包含M+1行，前M行每行包含一个菜名（按菜名在原菜单的顺序排序）。第M+1行是人均消费，结果保留两位小数。 如果无解的情况则只输出0.00 样例 1 输入： 4 3 3 fish 30 1 1 chicken 18 1 1 bean 12 0 0 meat 14 1 1 2 1 2 1 复制 输出： chicken bean meat 11.73

// n个值，选择m个的所有组合打出来

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

struct node{
    string name;
    //价格
    int price;
    //是否荤菜
    bool isMeat;//1,0
    //是否辛辣
    bool isSpicy;//1,0
};

void combine(int n, int m, int start, vector<int>& path, vector<vector<int>>& result) {
    if (m == 0) {
        result.push_back(path);
        return;
    }
    for (int i = start; i < n; i++) {
        path.push_back(i);
        combine(n, m - 1, i + 1, path, result);
        path.pop_back();
    }
}

int main() {
    int N,M,K;
    cin>>N>>M>>K;
    getchar();
    vector<node> menu;
    for(int i=0;i<N;i++){
        node tmp;
        cin>>tmp.name>>tmp.price>>tmp.isMeat>>tmp.isSpicy;
        menu.push_back(tmp);
    }
    vector<int> path;
    vector<vector<int>> result;
    combine(N, M, 0, path, result);

    vector<int> aa;
    float bb = 12;
    float avg =0.00f;
    for (auto& combination : result) {
        int totalPrice = 0;
        for (auto& num : combination) {
            totalPrice += menu[num].price;
        }
        avg = (float)totalPrice*0.8 / K;
        if (abs(avg -12) <bb) {
            bb=abs(avg -12);
            aa=combination;
        }
    }

        for (auto& num : aa) {
            cout << menu[num].name << endl;
        }
        printf("%.2f\n",avg);
    return 0;
}