首页 / 题库

P14014 - 2.1.4 Healthy Holsteins 健康的好斯坦奶牛

算法入门
通过次数1 提交次数1 内存限制 128MB 时间限制1秒

描述

农民约翰以拥有世界上最健康的奶牛为骄傲。为了保持奶牛的健康,他需要给奶牛喂食含有足够维他命的饲料。已知奶牛每天需要的各种维他命的最低摄入量,以及市面上可购买的每种饲料所含的各种维他命的量。约翰希望选择**最少种类**的饲料,使得这些饲料提供的每种维他命总量都不低于奶牛的最低需求量。

请你帮助约翰找出需要购买哪些种类的饲料,使得饲料种数最少,并且在这些饲料的编号按字典序最小的方案中输出。

输入

- 第 1 行:一个整数 $ V ( 1 \le V \le 25 )$,表示维他命的种类数。
- 第 2 行:$ V $ 个整数,表示奶牛每天需要的每种维他命的最低量(每个数在 1 到 1000 之间)。
- 第 3 行:一个整数 $ G ( 1 \le G \le 15 )$,表示可供选择的饲料种数。
- 接下来 $ G $ 行,每行包含 $ V $ 个整数,表示第 $ i $ 种饲料(编号从 1 开始)所含的每种维他命的量。

输出

输出一行,首先输出一个整数 $ P $,表示所需的最少饲料种数;然后输出 $ P $ 个整数,表示所选择的饲料编号(按从小到大排列)。如果有多种方案达到最少种数,则输出饲料编号字典序最小的方案(即编号序列最小)。

样例

  • 复制
  • 复制

提示

### 样例说明

奶牛需要 4 种维他命,最低量分别为 100, 200, 300, 400。
共有 3 种饲料:
- 饲料 1:50 50 50 50
- 饲料 2:200 300 200 300
- 饲料 3:900 150 389 399

选择饲料 1 和 3 时,维他命总量为 (950, 200, 439, 449),满足最低要求,共 2 种。
选择饲料 2 和 3 时,总量为 (1100, 450, 589, 699),也满足。
两种方案都是 2 种饲料,但字典序 `1 3` < `2 3`,因此输出 `2 1 3`。

## 数据范围与约定

- $ 1 \le V \le 25 $
- $ 1 \le G \le 15 $
- 每种维他命需求量及饲料含量均为 1 到 1000 之间的整数。
- 保证至少存在一种方案满足奶牛需求。

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36