SZ#G6KP28. 【GESP强化 六级】餐馆订单

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB
    ID: 11572 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 普及- 上传者: 标签>GESPGESP强化C++c++编程题背包问题完全背包方案唯一性2星

题目描述

小珅在餐馆担任服务员,最近经常有顾客只告诉他订单总价,却不直接说点了哪些菜。逐一推算每份订单很费时间,请你帮助他根据菜单中每种菜的价格和订单总价,还原顾客可能点了哪些菜。

每种菜都可以点任意多份。对于一份给定的订单总价,可能不存在任何点菜方案,也可能恰好有一种方案,还可能有多种方案。

输入格式

第一行包含一个整数 nn1n1001\le n\le100),表示菜单中的菜品数量。

第二行包含 nn 个正整数 c1,c2,,cnc_1,c_2,\ldots,c_n,表示各菜品的价格,每种菜的价格不超过 10001000

第三行包含一个整数 mm1m10001\le m\le1000),表示订单数量。

第四行包含 mm 个整数。每个整数 ss1s300001\le s\le30000)表示一份订单的总价。

输出格式

对每份订单输出一行:

  • 如果恰好存在一种方案,按非递减顺序输出该方案中各份菜品的编号;同一种菜点了多份时,编号也要重复输出。菜单中的第一种菜编号为 11
  • 如果没有任何方案,输出 Impossible
  • 如果存在两种或更多不同方案,输出 Ambiguous
3
4 5 8
3
11 13 14
Impossible
Ambiguous
1 2 2
6
215 275 335 355 420 580
1
1505
Ambiguous
2
465 126
2
187 46
Impossible
Impossible

说明/提示

数据范围与约定

  • 1n1001\le n\le100
  • 1ci10001\le c_i\le1000
  • 1m10001\le m\le1000
  • 1s300001\le s\le30000