农民约翰以拥有世界上最健康的奶牛为骄傲。为了保持奶牛的健康,他需要给奶牛喂食含有足够维他命的饲料。已知奶牛每天需要的各种维他命的最低摄入量,以及市面上可购买的每种饲料所含的各种维他命的量。约翰希望选择最少种类的饲料,使得这些饲料提供的每种维他命总量都不低于奶牛的最低需求量。
请你帮助约翰找出需要购买哪些种类的饲料,使得饲料种数最少,并且在这些饲料的编号按字典序最小的方案中输出。
输出一行,首先输出一个整数 P ,表示所需的最少饲料种数;然后输出 P 个整数,表示所选择的饲料编号(按从小到大排列)。如果有多种方案达到最少种数,则输出饲料编号字典序最小的方案(即编号序列最小)。
4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399
2 1 3
奶牛需要 4 种维他命,最低量分别为 100, 200, 300, 400。 共有 3 种饲料:
选择饲料 1 和 3 时,维他命总量为 (950, 200, 439, 449),满足最低要求,共 2 种。
选择饲料 2 和 3 时,总量为 (1100, 450, 589, 699),也满足。
两种方案都是 2 种饲料,但字典序 1 3 < 2 3,因此输出 2 1 3。
USACO