#P1293. Duty Free Shop
Duty Free Shop
描述
佩德罗前往欧洲参加国际信息学奥林匹克竞赛,现在正准备回家。因为他所有的朋友都让他带些礼物,所以他买了两大袋巧克力(一袋是Mindt品牌的,一袋是Lilka品牌的)。这两袋巧克力,每袋都装有一定数量的小巧克力。购买这两大袋巧克力比购买单独的小盒巧克力要便宜得多。在家里,佩德罗有一些他在其他旅行中留存下来的空巧克力盒。佩德罗打算把他刚买的巧克力分装到这些小盒子里,然后送给朋友们。
佩德罗一开始往小盒子里装巧克力,就意识到了一个大问题:由于他有两种不同品牌的巧克力,如果他把不同品牌的巧克力混装在一个小盒子里,收到这个小盒子的朋友就会发现佩德罗省钱的小伎俩,并且会不高兴。
你必须帮助可怜的佩德罗把巧克力分装到小盒子里,使得每个小盒子都完全装满,并且每个盒子里只装一种品牌的巧克力。不过,可能会有一些巧克力不装到任何盒子里(佩德罗会自己留着这些巧克力)。
输入
输入包含该问题的多个实例。每个实例由三行组成。第一行包含两个整数和,分别表示佩德罗购买的Mindt巧克力的数量和Lilka巧克力的数量()。下一行包含一个整数,表示佩德罗拥有的小盒子的数量()。第三行包含个整数,表示第个盒子的容量(即装满那个盒子所需的巧克力数量)。当时,表示输入结束。
输出
对于输入的每个实例,你的程序必须输出一行。如果按照问题描述的方式能够分装巧克力,打印出装满Mindt巧克力的盒子的数量,后面跟一个空格,再后面是按升序排列的盒子编号列表。列表中的每个盒子编号后面都要跟一个空格。如果无法分装巧克力,打印 “Impossible to distribute”。如果存在多个解决方案,打印任意一个即可。
输入数据1
12 9
4
5 2 8 5
100 120
5
21 32 110 54 3
0 0
输出数据1
3 1 2 4
Impossible to distribute
来源
2002年南美洲竞赛