[JOIST 2023] 曲奇 / Cookies

Luogu

IDLGP9339

Time1000ms

Memory1024MB

DifficultyP7

2023Special JudgeO2优化背包 DP二分图bitsetJOISC/JOIST（日本）

莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。 + 对于每个盒子，其中的饼干种类应不同。 + 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可以将所有饼干包装在盒子中，则您的程序应输出最少的盒子数量。 ## Input 从标准输入读取以下数据。 > $N$ > $A _ 1 \ A _ 2 \ \cdots \ A _ N$ > $M$ > $B _ 1 \ B _ 2 \ \cdots \ B _ M$ ## Output 如果可以将所有的饼干装入盒子并且满足上述条件，则设 $x$ 是所需的盒子数，$c_k$ 是第 $k$ 个盒子中的饼干数 $(1≤k≤x)$，$v_{k,1},v_{k,2},⋯ ,v_{k,c_k}$ 是第 $k$ 个盒子中的饼干种类。请将这些数字按以下格式编写到标准输出。 > $x$ > $c _ 1 \ v _ {1, 1} \ v _ {1, 2} \ \cdots \ v _ {1, c _ 1}$ > $c _ 2 \ v _ {2, 1} \ v _ {2, 2} \ \cdots \ v _ {2, c _ 2}$ > $\vdots$ > $c _ x \ v _ {x, 1} \ v _ {x, 2} \ \cdots \ v _ {x, c _ x}$ 在此，使用的盒子数量 $x$ 应该是可能的最小数量。如果有多种方式可以满足条件地将饼干装入盒子，请输出其中任何一种方法。如果无法将所有饼干包装在盒子中以满足条件，输出 $-1$。 [samples] ## Note #### 【样例解释 #1】对于该样例输入，可以按照以下方式将 $7$ 个饼干装入 $3$ 个盒子中满足条件： + 将第 $1$ 类和第 $7$ 类的饼干装入第一个盒子中。每种类型放 $1$ 个。 + 将第 $2$ 类和第 $6$ 类的饼干装入第二个盒子中。每种类型放 $1$ 个。 + 将第 $3$ 类、第 $4$ 类和第 $5$ 类的饼干装入第三个盒子中。每种类型放 $1$ 个。因为不能用少于或等于 $2$ 个盒子来包装 $7$ 个饼干，所以以上方法是正确的。判断为正确答案。还有其他正确方法。 **【数据范围】** 对于所有测试数据，满足 $1 \leq N \leq 15 000$，$A _ i \geq 1$（$1 \leq i \leq n$），$A _ 1 + A _ 2 + \cdots + A _ N \leq 15 000$，$1 \leq M \leq N$，$1 \leq B _ j \leq N$（$1 \leq j \leq M$），$B _ j < B _ {j + 1}$（$1 \leq j \leq M - 1$），保证所有输入均为整数。 | **子任务编号** | **分值** | **限制** | | :----------: | :----------: | :----------: | | $1$ | $6$ | $N \leq 500$，$A _ i = 1$（$1 \leq i \leq N$） | | $2$ | $7$ | $N \leq 500$，$M = 1$ | | $3$ | $12$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 15$ | | $4$ | $45$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 500$ | | $5$ | $15$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 3000$ | | $6$ | $15$ | 没有额外的限制 | Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

Samples

Input #1

7
1 1 1 1 1 1 1
3
1 2 3

Output #1

Input #2

Output #2

-1

Input #3

7
5 4 4 2 1 1 1
2
2 6

Output #3

7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2023] 曲奇 / Cookies",
    "description": {
      "content": "莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。 + 对于每个盒子，其中的饼干种类应不同。 + 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。 编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9339"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。\n\n+ 对于每个盒子，其中的饼干种类应不同。\n\n+ 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。\n\n编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments