[传智杯 #4 决赛] 游戏

Luogu

IDLGP8199

Time1000ms

Memory512MB

DifficultyP4

模拟O2优化传智杯

喷火刚刚跳伞落地，周围危机四伏，他的手中有一个初始背包，他捡到的所有物资都会装在这个背包里，游戏地图被简化为一个 $n \times m$ 的网格图，每个格子里要么是物资，要么是敌人。物资分为主/副武器和弹药，其中弹药又分为子弹与投掷物。每种武器会对应使用某种子弹。例如：Beryl M762 突击步枪使用 7.62mm 子弹，M416 突击步枪使用 5.56mm 子弹，而 AKM 突击步枪也使用 7.62mm 子弹。当喷火走到一个含有物资的格子的时候，他会拾起地上的物资并放入背包。但背包容量有限，因此当背包装满的时候，他将会扔掉一部分物资以装下新的物资。他将按照以下规则丢弃物资： 1. 如果捡到的是武器，那么按照霰弹枪>突击步枪>射手步枪>栓动步枪>空手的优先级进行替换。优先替换主武器，且主武器优先级必须严格高于副武器。如果替换主武器，那么替换下来的主武器被**直接丢弃**，不再用其替换副武器。 2. 若有不需要的子弹（指主副武器均不使用的子弹），最优先丢掉这些子弹，直至空间足够装下新的物资。 3. 若丢掉全部不需要子弹后空间仍旧不足，或有多种不需要的子弹，优先丢掉最晚拾取时间最早的弹药（包括主副武器使用的子弹和投掷物），直至空间足够装下新的物资（需要注意的是，即使新物资是「不需要的子弹」，在丢掉所有原有的「不需要的子弹」后如果背包空间还是不够，则喷火依然会丢掉其他弹药直到捡起所有「不需要的子弹」）。 4. 无论捡到的是新物资，还是已经有的物资，该物资的最晚拾取时间都将被更新为当前时间点。 5. 武器最多同时持有两种，即主/副武器，同优先级的主/副武器不进行替换。每个格子的物资只会拾取一次。当第二次进入某个格子的时候，物品不会刷新，即不会捡起上次在这个格子丢掉的物品，也不会再次捡到初始时的物品。当喷火走到含有敌人的格子的时候，他会与敌人进行战斗，他的战斗力很强悍，只需要有足够的子弹即可消灭敌人。每个敌人有两个参数 $a,b$，代表需要消耗 $a$ 发主武器子弹，若主武器子弹不够，则不消耗主武器子弹，而消耗 $b$ 发副武器子弹。若主副武器均没有足够子弹，则喷火被敌人反杀，然后敌人会在喷火的盒子上做蹲起嘲讽他。每个格子的敌人只会出现一次。如果第二次进入某一个有敌人的格子，则什么都不会发生。现在，喷火跳在了第一行第一列的格子上，ATA_Radio_STN 已经为喷火摸清了地图形势，而 sltheen 会给喷火下指示，喷火想知道，当他执行完最后一条指示之后，他是否还存活，若存活，按照最晚拾取时间时间从早到晚，输出背包内物品种类和数量，若死亡，输出他死亡格子的坐标。下附可能出现的物资、物资类别、物资使用的子弹种类、物资所需空间以及物资对应编号。武器： | 武器名称 | 武器类型| 使用的子弹类型 | 编号 | | --- | --- | --- | ---| | 空手 | 空手 | N/A | 0| |BerylM762|突击步枪|7.62mm子弹|1| |AKM|突击步枪|7.62mm子弹|2| |SKS|射手步枪|7.62mm子弹|3| |Kar98K|栓动步枪|7.62mm子弹|4| |M416|突击步枪|5.56mm子弹|5| |MK12|射手步枪|5.56mm子弹|6| |Mini14|射手步枪|5.56mm子弹|7| |S686|霰弹枪|12号霰弹|8| |DBS|霰弹枪|12号霰弹|9| 弹药 |弹药名称| 类型 | 占用空间 | 编号 | | - | - | - | - | |FragGrenade|投掷物| 5 | 10| |SmokeGrenade| 投掷物 | 4| 11| |MolotovCocktail |投掷物 | 3 | 12| |Flashbang |投掷物 | 2 | 13| |7.62mm |子弹 |0.2| 14| |5.56mm| 子弹| 0.1 |15| |3in（12号霰弹）| 子弹| 0.5| 16| 请注意，上表中子弹的「占用空间」表示一发子弹所占用的空间。另外，敌人在地图上的编号为 17。 ## Input 第一行有四个整数，依次表示地图行数 $n$，列数 $m$，背包容量 $k$，和 sltheen 会下达的指令条数 $t$。接下来的 $n\times m$ 行中，第 $i$ 行代表第 $\lfloor\frac{i - 1}{n}\rfloor+1$ 行，第 $(i - 1)\%n+1$ 列的地图情况，其中 $i \% n$ 表示 $i$ 除以 $n$ 的余数： - 此处若是物资，则本行有两个空格隔开的整数，为物资编号 $x$ 和物资数量 $y$，物资编号见「题目描述」中表格的最后一列（如果该物资是枪，则保证 $y = 1$）； - 若此处是敌人，则本行有三个空格隔开的整数，第一个整数为 $17$，代表敌人，接下来两个整数依次表示敌人的 $a, b$ 两个参数。接下来 $t$ 行，每行一个整数 $op$，表示 sltheen 为喷火下达的指令的移动方向：1 代表向上，2 代表向下，3 代表向左，4 代表向右。（第一行第一列是地图的左上角，最后一行第一列是地图的左下角） ## Output 如果喷火死亡，则输出两个数 $u, v$，代表喷火在第 $u$ 行第 $v$ 列死亡。若喷火未死亡，先输出两行，第一行为主武器编号，第二行为副武器编号，之后输出若干行，每行为两个整数整数，中间用空格隔开，第一个整数为物资名称，第二个整数为其数量，按照最后捡到时间从早到晚排序。 [samples] ## Background 小智正在看 B 站非著名 up 主脚踢喷火幼儿园（下称喷火）和他的朋友 ATA_Radio_STN 和 sltheen 正在游玩著名游戏《PLAYERUNKNOWN’S BATTLEGROUNDS》（绝地求生：大逃杀）。 ## Note ### 数据规模与约定对于全部的测试点，保证： - $1 \leq n, m \leq 100$，且 $1 \leq n \times m \leq 100$。 - $1 \leq k \leq 500$，$1 \leq t,a,b \leq 200$。 - $1 \leq x \leq 16$，$1 \leq y \leq 5000$。 - $1 \leq op \leq 4$。 - 数据保证每个格子内只有一种物资（或一个敌人），且背包能够装下任意一格的物资。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[传智杯 #4 决赛] 游戏",
    "description": {
      "content": "喷火刚刚跳伞落地，周围危机四伏，他的手中有一个初始背包，他捡到的所有物资都会装在这个背包里，游戏地图被简化为一个 $n \\times m$ 的网格图，每个格子里要么是物资，要么是敌人。 物资分为主/副武器和弹药，其中弹药又分为子弹与投掷物。每种武器会对应使用某种子弹。例如：Beryl M762 突击步枪使用 7.62mm 子弹，M416 突击步枪使用 5.56mm 子弹，而 AKM 突击步枪也使",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8199"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "喷火刚刚跳伞落地，周围危机四伏，他的手中有一个初始背包，他捡到的所有物资都会装在这个背包里，游戏地图被简化为一个 $n \\times m$ 的网格图，每个格子里要么是物资，要么是敌人。\n\n物资分为主/副武器和弹药，其中弹药又分为子弹与投掷物。每种武器会对应使用某种子弹。例如：Beryl M762 突击步枪使用 7.62mm 子弹，M416 突击步枪使用 5.56mm 子弹，而 AKM 突击步枪也使...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments