#P113. ensokyo Izakaya

ensokyo Izakaya

题目描述

注意:请勿代入游玩本题原型游戏的经验阅读题目描述,因为其中存在大量魔改。

HH 是车万夜雀食堂某分店的店员,负责招揽客人以及帮健忘的老板娘算账。老板娘给小 HH 的新手教程如下:

I. 菜品和客人的基本介绍:

食堂有 nn 个座位。每天初始营业轮数为 1212 ,最后一个营业轮结束后,当日营业立刻结束。食堂的菜单上有 mm 道菜,第 jj 道菜的价格为 wjw_j ,具有 vjv_j 个标签。菜品的价格互不相同

客人分普通客人和特殊客人两种,每位特殊客人都有一种正面技能和一种负面技能。每名客人都有三项信息:身份,好恶和预算。普通客人的身份以 00 标记,特殊客人一共有 55 位,以 1,2,3,4,51,2,3,4,5 中的一个独立编号标记;客人的好恶将用标签表示,与菜品的标签系统一致,普通客人有且只有 11 种喜好,而特殊客人可以具有多种喜好和多种厌恶(也可能没有)。客人对菜品的喜好度将影响他们支付的小费(具体计算方式见第III部分)。

II. 食堂的营业流程:

ii 轮开始时,小 HH 会招揽 kik_i 名客人依次进入食堂到队尾排队。队列中前 nn 名客人会依次入座(少于 nn 人则全部依次入座),其余客人继续排队等候,留到下一轮。当日营业结束时,还在排队的客人将会全部离开。每位特殊客人每天至多到店 11

完成入座后,座位上的所有客人会依次点餐。结账时,跳过中途离开的客人(具体说明见第III部分)和空座位,按入座顺序使用技能(如有)并结账,每一位客人在结账后都会立刻离开。

所有座位上的客人离开后,该轮结束,进入下一轮,如此循环。

点餐或结账阶段中,所有正在生效的技能按照技能被使用的先后顺序依次触发效果。

III. 点餐规则:

普通客人点餐时总是先考虑预算,再考虑喜好:

  • 若菜单上没有不超过自己预算的菜,则会当场离开;
  • 否则,优先选择菜单上具有自己喜好标签的菜品中最贵的;
  • 若菜单上没有菜品具有自己的喜好标签,则选择最便宜的菜品。
  • 规定普通客人对有自己喜好标签的菜品喜好程度为 11 ,没有则为 00 ,不考虑标签数量。

特殊客人不会主动选择菜品,而是由老板娘自行选择:

  • 选择时如有相关技能生效,那么优先考虑技能影响;
  • 此后,老板娘会在技能影响下选择菜单上该客人喜好程度最大的一道菜品(如有多道喜好程度相同,则选择价格最高的),喜好程度具体计算方式见下文;
  • 老板娘会在最终选定菜品后再把特殊客人对菜品的喜好程度 +1+1 ,这一效果不受任何技能影响。

普通客人和特殊客人一轮都只会点餐 11 次。

一名特殊客人对菜品本身的喜好程度,需要按顺序依次计算以下 33 部分求得:

  • 初始值:这道菜包含该客人的喜好标签数量和厌恶标签数量的差值;

  • 预算的影响:若菜品价格超预算但不超过预算的 22 倍,则喜好程度会 1-1 ;若菜品价格超过预算的 22 倍,这道菜的喜好程度将直接变为 2-2

  • 技能的影响。

    IV. 结账规则:

每位特殊客人在他自己结账前会先根据菜品的喜好程度使用技能。

若菜品具有的喜好程度大于等于 33 和该客人具有喜好标签总数的最小值,那么客人将使用自己的正面技能;若菜品具有的喜好程度小于 00 ,那么客人将使用自己的负面技能,且立刻离开,不付钱。

每名客人结账时支付的小费等于(菜品价格 ×\times 喜好程度 ×10%\times \,10\%下取整 ,小费不计入客人的预算范围。从每名客人获得的收入即为菜品价格和小费的总和。

V. 特殊客人技能一览:

  • 11

正面技能:之后 66 轮(不包括当前轮,下同),特殊客人对含标签 00 的菜品的喜好程度至少为 22 ,普通客人视标签 00 为喜好标签(注意普通客人仍然优先考虑预算)。

负面技能:之后 33 轮,所有客人对菜品的喜好程度至多为 11

  • 22

正面技能:营业轮数增加 11 轮,但是超出 1212 轮的轮次中小 HH 不会招揽客人。

负面技能:立刻驱逐座位上的所有客人,被驱逐的客人不会付钱或使用技能。

  • 33

正面技能:之后 33 轮,只有菜单上最贵的菜品可选,所有客人的预算变为无限大,且对该菜品的喜好程度至少为 1-1

负面技能:之后 33 轮,只有菜单上最便宜的菜品可选(这可能导致特殊客人触发负面技能)。

  • 44

正面技能:之后 66 轮,客人支付的小费变为原来的 22 倍。

负面技能:立刻从菜单上永久移除其中最贵的 22 道菜品。

  • 55

正面技能:抵消下一次特殊客人的负面技能(但是该特殊客人仍然不付钱)。

负面技能:下一轮特殊客人无法使用任何正面技能。


HH 每天都会准确记录食堂当日的菜单、座位数,以及他每一轮招揽的全部客人的信息。但是小 HH 的智商为 99 ,无法在记录的同时算清收入。作为食堂的新店员,请你根据小 HH 一天的营业信息记录,编程帮助他完成算账。

输入格式

第一行两个整数 n,m(1n1000,3m20)n,m\,(1\leq n\leq 1000,3\leq m\leq 20) ,表示当日食堂的座位数和菜品数。

接下来 mm 行,每行首先输入两个整数 wi,vi(1wi104,0vi31)w_i,v_i\,(1\leq w_i\leq10^4,0\leq v_i\leq31) ,表示第 ii 道菜品的价格和标签数;然后输入 viv_i 个非负整数,描述该菜品的全部标签,保证一道菜品的标签不出现重复。

接下来 1212 组输入,每组输入描述一轮的揽客情况。对于每组输入:

  • 第一行一个整数 ki(0ki13n,1ki20n)k_i\,(0\leq k_i\leq 13n,1\leq \sum k_i\leq 20n) ,描述这一轮小 HH 招揽客人的数量。
  • 接下来的 kik_i 行,每行描述一名客人:

首先输入两个整数 opi,ci(0opi5,1ci104)op_i,c_i\,(0\leq op_i \leq 5,\,1\leq c_i\leq 10^4) ,描述该客人的身份和预算。

opi=0op_i=0 ,再输入一个整数 x(0x30)x\,(0\leq x\leq 30) ,描述该普通客人的喜好标签;

opi>0op_i>0 ,再输入两个整数 sj,tj(0sj,tj30)s_j,t_j\,(0\leq s_j,t_j\leq 30) ,表示该特殊客人的喜好标签和厌恶标签数量,之后依次输入 sjs_jtjt_j 个非负整数,描述该特殊客人的喜好和厌恶标签。

除去题目描述提及的限制之外,数据保证每道菜品自身具有的标签不重复,每位客人自身的好恶标签不重复、不冲突,任意菜品和顾客好恶的标签大小不超过 3030

输出格式

一行,输出一个整数,表示当日总收入。

输入输出样例 #1

输入 #1

3 3
10 2 0 1
20 1 1
30 2 1 2
4
0 20 1
0 20 0
3 4 3 0 0 1 2
0 8 0
1
4 8 0 1 0
0
0
0
0
0
0
0
0
0
5
1 10 1 0 0
2 10 1 0 0
0 10 2
0 8 2
5 10 0 2 0 1

输出 #1

80

说明/提示

在本样例中,食堂有 33 个座位,33 道菜品。

11:小 HH 招揽 44 位客人,前 33 位入座,第 44 位排队。

本轮入座的第 11 位客人为普通客人,预算为 2020 ,喜好标签为 11 。所有菜品都具有标签 11 ,第 33 道菜价格超出预算,因此第 11 位客人选择第 22 道菜。第 22 位客人也为普通客人,喜好标签为 00 ,所以选择预算以内唯一有标签 00 的第 11 道菜。第 33 位客人为 33 号特殊客人,喜好标签为 0,1,20,1,2 。尽管第 1,31,3 道菜具有的标签均可以提供 22 喜好程度,但是由于所有菜品都超出预算 22 倍,所以所有菜品的喜好程度最终都为 2-2 ,再加上老板娘提供的 +1+1 后仍都小于 00

本轮入座的第一位客人支付 20+20×10%=2220+20\times10\%=22,第二位客人支付 10+10×10%=1110+10\times10\%=11,第三位客人使用负面技能且不付钱,本轮收入 3333

22:小 HH 招揽 11 位客人,排队的 11 位客人先入座,之后本轮进入食堂的 11 位客人入座。

本轮入座的第 11 位客人的预算低于所有菜品,因此直接离开。第 22 位客人为 44 号特殊客人,由于 33 号特殊客人的负面技能,老板娘必须选第 11 道菜,菜品标签提供 1-1 的喜好程度,预算超出 22 倍以内喜好程度 1-1 ,加上老板娘提供的 +1+1,最终喜好程度为 1-1

本轮入座的第 11 位客人直接离开,第 22 位客人使用负面技能且不付钱,本轮收入为 00

3113-11:小 HH 不招揽客人,也无人排队,因此无人用餐,收入为 00

33 号特殊客人的技能从第 55 轮开始不再生效。

1212:小 HH 招揽 55 位客人,前 33 位入座,第 4,54,5 位排队。

本轮第 11 位客人为 11 号特殊客人,同上一轮只能选第 11 道菜,喜好程度为 1+0+1=21+0+1=2,大于其总喜好标签数。第 22 位客人为 22 号特殊客人,情形与上一位完全相同。第 33 位客人为普通客人,只能点第 11 道菜品。

本轮前两位客人依次使用正面技能并支付10+10×2×10%=1210+10\times2\times10\%=12 ,第三位客人支付 1010 ,总收入 3434

由于 22 号特殊客人的正面技能,营业增加一轮。

1313 :小 HH 不招揽客人,排队的 22 位客人入座。

本轮第 11 位客人为 55 号特殊客人,同上一轮只能选第 11 道菜,这道菜具有 00 号标签,所以受 11 号特殊客人的技能影响。第 11 位客人虽然在技能影响下喜好该菜品,但是预算不足,因此会直接离开。第 22 位客人为 55 号特殊客人,受技能影响,对该菜品本身的喜好度为 max(2+0,2)max(-2+0,2) ,再加上老板娘的 +1+1 ,最终喜好度为 33

本轮第 11 位客人不付钱,第 22 位客人使用正面技能并支付 10+10×3×10%=1310+10\times3\times10\%=13 ,总收入 1313

营业结束,本日总收入为 33+34+13=8033+34+13=80