编程问题智能生成器

## 问题标题
括号平衡校验与错误定位

## 问题描述
给定一行字符串，其中可能包含多种字符。仅将三类括号字符视为需要配对的有效字符：小括号 ()、中括号 []、大括号 {}。请判断字符串中的括号是否“成对且嵌套合法”。

- 若所有括号都能正确匹配，输出 OK。
- 若存在不合法的括号，输出 ERR i，其中 i 为首个导致不合法的字符的索引（从 0 开始，按原字符串计数）。

不合法的两种情况与“首个错误索引”定义如下：
1. 在扫描过程中遇到某个右括号时，栈顶不是对应的左括号（类型不匹配）或栈为空（没有可匹配的左括号），则该右括号的索引为首个错误索引。
2. 扫描完整个字符串后仍有未匹配的左括号，则取这些未匹配左括号中“最早出现”的那个左括号的索引作为首个错误索引（即未匹配左括号中最小的索引）。

注意：
- 非括号字符应被忽略，不参与匹配，也不会单独构成错误。
- 字符索引按原始字符串的每个字符从左到右计数。

## 技术要求
- 只能使用常规数据结构与语言自带容器；不得使用正则引擎做整体匹配替代。
- 时间复杂度要求为 O(n)，空间复杂度 O(n)，其中 n 为字符串长度。
- 需支持字符串长度最大至 100000。
- 括号类型严格限定为 ()、[]、{}，其余字符一律忽略。
- 输出格式严格遵循“OK”或“ERR i”，其中 i 为十进制整数、0-based 索引。

可实现形式（任选其一，或按平台要求）：
- 从标准输入读取一行字符串，按要求打印输出。
- 实现函数 solve(s: string) -> string，返回 "OK" 或 "ERR i"。

## 输入输出示例
示例 1
输入:
([{}])

输出:
OK

示例 2
输入:
([)]

输出:
ERR 2
说明: 索引 2 处的右括号 ')' 期望匹配 '['，类型不符。

示例 3
输入:
(()abc

输出:
ERR 0
说明: 扫描结束仍有未匹配的 '('，且索引最小的是 0。

示例 4
输入:
abc]def

输出:
ERR 3
说明: 索引 3 处出现多余的右括号 ']'。

示例 5
输入:
 

输出:
OK
说明: 空字符串（或仅空白）没有括号，视为合法。

## 测试用例
请确保以下用例全部通过，并可在此基础上补充自测：

1) 基本匹配
输入: ()[]{}   
输出: OK

2) 嵌套匹配
输入: ({[a]})   
输出: OK

3) 交叉错误
输入: ([)]   
输出: ERR 2

4) 多余右括号（开头即错误）
输入: ]   
输出: ERR 0

5) 多余左括号（结尾残留）
输入: (((   
输出: ERR 0

6) 忽略非括号字符
输入: 1+(2*[3-{4/5}])   
输出: OK

7) 空字符串
输入:    
输出: OK

8) 连续相同括号匹配
输入: [[]][]   
输出: OK

9) 末尾多一个右括号
输入: ([{}]]   
输出: ERR 5

10) 多个未匹配左括号时取最早出现者
输入: a(b[c{d}e)f[g   
输出: ERR 2
说明: 未匹配左括号有 '(' 索引 2 与 '[' 索引 12，取最小索引 2。

11) 中间错误后续不再考虑
输入: ({])}   
输出: ERR 2
说明: 索引 2 的 ']' 与 '{' 不匹配，首错即止。

12) 含空白与多字节字符（忽略非括号）
输入: （注意这不是半角括号） [汉字]{emoji🙂}(ok)   
输出: OK
说明: 只有半角 []{}() 参与匹配。

提示：上述用例中的空白或多字节字符在不同语言的输入读取中需确保不破坏索引计数（以字节或字符为单位的一致性，通常以字符为准）。

## 评分标准
- 正确性（60%）
  - 能正确判断合法与不合法情况。
  - 精准输出首个错误索引，符合两类错误定义。
- 复杂度与性能（10%）
  - 时间 O(n)、空间 O(n)，可在 n=100000 下稳定运行。
- 边界与鲁棒性（15%）
  - 忽略非括号字符、正确处理空字符串、只有左括号或只有右括号等情况。
- 代码质量（10%）
  - 结构清晰、命名规范、可读性好，无冗余逻辑。
- 测试完备性（5%）
  - 至少覆盖本题提供的测试用例，并包含自定义补充用例。

## 解决思路
- 用栈维护未匹配的左括号及其索引。元素形式：(char, index)。
- 建立映射：右括号到对应左括号，例如 {')':'(', ']':'[', '}':'{'}。
- 线性扫描字符串：
  - 若当前字符是左括号之一，入栈 (char, i)。
  - 若是右括号之一：
    - 若栈为空，返回 "ERR i"。
    - 取栈顶，若类型不匹配（映射不相等），返回 "ERR i"。
    - 否则匹配成功，弹栈继续。
  - 其余字符忽略。
- 扫描结束：
  - 若栈为空，返回 "OK"。
  - 若栈不为空，从栈中找到未匹配左括号的最小索引（可直接取栈底元素的索引，或遍历栈取最小值），返回 "ERR minIndex"。
- 复杂度分析：
  - 每个括号最多入栈一次、出栈一次，整体 O(n) 时间，栈空间最坏 O(n)。
- 容易出错点：
  - 忽略非括号字符时仍需正确累计索引。
  - 注意“首个错误”的定义：一旦遇到不匹配的右括号，立刻返回；只有在完全扫描后才考虑未匹配左括号并取最早出现者。

## 问题标题
并发读写锁管理器：支持升级、死锁检测、超时与公平策略

## 问题描述
实现一个多资源的并发读写锁管理器（Lock Manager），支持以下能力：
- 基本读写锁（S 共享、X 独占）与同一资源上的 S→X 升级、X→S 降级（本题只要求升级）。
- 公平策略：写者优先（当等待队列中存在写者或升级请求在队首时，后续到达的读者不再被立即授予）。
- 死锁检测：基于等待图（Wait-For Graph）周期检测，发现后按策略选择牺牲者并中止其事务。
- 超时：等待超过指定超时的锁请求导致事务整体回滚（释放已持有的全部锁）。
- 多资源：事务可对多个资源加锁；需正确处理跨资源的等待与死锁。

你需要编写一个程序，按输入脚本驱动该锁管理器的行为，输出每一步的可观测事件（如授予、排队、阻塞、超时、死锁与中止等）。该题旨在考察并发控制的高级概念与工程实现，包括数据结构设计、调度公平性、升级语义、死锁检测与恢复策略。

注：为便于判题与复现，本题使用“事件驱动 + 逻辑时钟”的模拟方式；你可以用多线程/协程实现内部并发控制，也可以用单线程事件驱动模拟，但必须满足技术要求的语义与输出。

## 技术要求
- 锁模型与兼容性
  - 模式：S（共享）、X（独占）。兼容性：S 与 S 兼容；X 与任意不兼容。
  - 升级：若事务 T 已持有资源 R 的 S，T 可发起对 R 的 X 的升级请求。升级请求被视为写者请求，插入队列头（高优先级），但需等待其他持有者释放。
  - 重入：禁止同一事务对同一资源重复获取相同模式（再次请求视作无效，应报错或忽略；推荐忽略并不输出事件）。
- 公平性
  - 写者优先：当某资源的等待队列队首为写者或升级请求时，后续到达的读者请求一律进入队列等待（不即时授予）。
  - 授予策略：在释放或中止后，按队列顺序尝试授予；若队首为写者/升级且可授予则授予；若队首为读者，则可批量授予一段连续的读者请求，直到队列遇到写者/升级为止。
- 死锁检测
  - 等待图构建：对每个因冲突而阻塞的请求 A→B 建边（A 等待持有冲突锁的事务 B）；升级请求对“其他持有该资源 S 的事务”建边。
  - 检测时机：在每次状态变化（LOCK/UNLOCK/TICK/ABORT/COMMIT）后进行；一旦发现环路，立刻选择牺牲者并中止（释放其所有锁，清除其队列项），然后继续尝试授予。
  - 牺牲者选择：优先级低者优先被中止；若优先级相同，锁持有数多者先中止；如仍相同，事务 ID 字典序更大者中止。
- 超时
  - 请求可指定超时时间（毫秒）。若从进入阻塞状态起等待时间超过超时，直接中止整个事务（释放其全部锁）。无限超时可用 TIMEOUT INF 表示或省略 TIMEOUT。
- 事务语义
  - BEGIN/COMMIT/ABORT：BEGIN 创建事务（可指定优先级，默认 0）；COMMIT 释放其全部锁并结束；ABORT 可由客户端发起，或由死锁/超时触发。
- 时间推进
  - 通过 TICK ms 推进逻辑时钟，驱动超时判断与随后的授予。
- 输出要求
  - 输出必须严格按照“输入事件发生后导致的可观测状态变化”的顺序打印，详见“输入输出示例”。
- 复杂度建议
  - 资源表与事务表：哈希表 O(1) 期望时间访问。
  - 每资源等待队列：双端队列。
  - 死锁检测：对当前等待图做一次 DFS/Tarjan/Kahn，O(V+E)，在规模上限内可接受。
- 可用语言
  - Python、Java、Go、Rust、C++ 等。并发实现可用线程/协程/异步事件均可，但行为需与规范一致。

## 输入输出示例
输入格式（逐行命令）：
- BEGIN <txId> [PRIORITY <p>]
- LOCK <txId> <resId> <mode> [TIMEOUT <ms>|TIMEOUT INF] [UPGRADE]
- UNLOCK <txId> <resId>
- COMMIT <txId>
- ABORT <txId>
- TICK <ms>
- END

输出事件（逐行）：
- GRANTED <txId> <resId> <mode>
- QUEUED <txId> <resId> <mode> [UPGRADE]        // 因公平策略进入队列但非直接冲突
- BLOCKED <txId> <resId> <mode> BY <tx1,tx2,...> // 直接冲突的阻塞者，按事务 ID 升序
- RELEASED <txId> <resId>
- TIMEOUT <txId> <resId> <mode>
- DEADLOCK <txa>-<txb>-...-<txa> CHOOSE <victimTxId>
- ABORT <txId> REASON <DEADLOCK|TIMEOUT|CLIENT>
- COMMIT <txId>
- TICK <now>                                     // 打印推进后的当前时间

说明：
- 对同一命令，先输出本命令直接产生的事件（如 GRANTED/QUEUED/BLOCKED），再在需要时进行死锁检测与后续事件（DEADLOCK/ABORT/GRANTED...）。
- TICK 后需输出当前逻辑时间（累计）。

示例（简要）：
输入
BEGIN T1
LOCK T1 A S
BEGIN T2
LOCK T2 A S
BEGIN T3
LOCK T3 A X
BEGIN T4
LOCK T4 A S
UNLOCK T1 A
UNLOCK T2 A
TICK 0
UNLOCK T3 A
TICK 0
END

输出
GRANTED T1 A S
GRANTED T2 A S
BLOCKED T3 A X BY T1,T2
QUEUED T4 A S
RELEASED T1 A
RELEASED T2 A
GRANTED T3 A X
TICK 0
RELEASED T3 A
GRANTED T4 A S
TICK 0

## 测试用例
用例 1：基础共享/独占与写者优先
输入
BEGIN T1
LOCK T1 A S
BEGIN T2
LOCK T2 A S
BEGIN T3
LOCK T3 A X
BEGIN T4
LOCK T4 A S
UNLOCK T1 A
UNLOCK T2 A
TICK 0
UNLOCK T3 A
TICK 0
END

期望输出
GRANTED T1 A S
GRANTED T2 A S
BLOCKED T3 A X BY T1,T2
QUEUED T4 A S
RELEASED T1 A
RELEASED T2 A
GRANTED T3 A X
TICK 0
RELEASED T3 A
GRANTED T4 A S
TICK 0

用例 2：升级导致的死锁
输入
BEGIN T1
LOCK T1 A S
BEGIN T2
LOCK T2 A S
LOCK T1 A X UPGRADE
LOCK T2 A X UPGRADE
TICK 0
END

期望输出
GRANTED T1 A S
GRANTED T2 A S
BLOCKED T1 A X BY T2
BLOCKED T2 A X BY T1
DEADLOCK T1-T2-T1 CHOOSE T2
ABORT T2 REASON DEADLOCK
GRANTED T1 A X
TICK 0

用例 3：经典 ABBA 死锁
输入
BEGIN T1
BEGIN T2
LOCK T1 A X
LOCK T2 B X
LOCK T1 B X
LOCK T2 A X
TICK 0
END

期望输出
GRANTED T1 A X
GRANTED T2 B X
BLOCKED T1 B X BY T2
BLOCKED T2 A X BY T1
DEADLOCK T1-T2-T1 CHOOSE T2
ABORT T2 REASON DEADLOCK
GRANTED T1 B X
TICK 0

用例 4：超时回滚
输入
BEGIN T1
LOCK T1 A X
BEGIN T2
LOCK T2 A X TIMEOUT 100
TICK 100
END

期望输出
GRANTED T1 A X
BLOCKED T2 A X BY T1
TIMEOUT T2 A X
ABORT T2 REASON TIMEOUT
TICK 100

用例 5：队首写者存在时的新读者排队、公平授予
输入
BEGIN T1
LOCK T1 A S
BEGIN T2
LOCK T2 A S
BEGIN T3
LOCK T3 A X
BEGIN T4
LOCK T4 A S
BEGIN T5
LOCK T5 A S
UNLOCK T1 A
UNLOCK T2 A
TICK 0
UNLOCK T3 A
TICK 0
END

期望输出
GRANTED T1 A S
GRANTED T2 A S
BLOCKED T3 A X BY T1,T2
QUEUED T4 A S
QUEUED T5 A S
RELEASED T1 A
RELEASED T2 A
GRANTED T3 A X
TICK 0
RELEASED T3 A
GRANTED T4 A S
GRANTED T5 A S
TICK 0

边界建议再自测：
- 同一事务对同一资源重复 LOCK S 或 LOCK X（应忽略或报错，不影响状态）。
- 升级请求到达时，资源等待队列已有写者。
- 多个循环同时存在的死锁检测（应一次至少打破一个环，建议循环处理直到无环）。

## 评分标准
- 正确性（50%）
  - 锁兼容性与授予规则正确（含批量授予读者）。
  - 写者优先策略严格执行。
  - 升级语义与队列位置处理正确。
  - 死锁检测与牺牲者选择符合规范。
  - 超时触发的事务回滚逻辑正确。
- 完整性与鲁棒性（20%)
  - 支持多资源与多事务同时操作。
  - 边界处理（重复请求、无效解锁、已结束事务操作等）健壮。
  - 输出顺序与格式严格符合要求。
- 性能（15%）
  - 数据结构设计合理；在大规模事件下仍可在限定时间内完成（如 10^5 条命令）。
  - 死锁检测开销控制（按需触发或增量维护）。
- 工程实现（10%）
  - 代码结构清晰、模块化（事务表、资源表、等待图等）。
  - 并发安全（若使用多线程）或事件驱动逻辑一致性（若单线程）。
- 额外加分（5%）
  - 支持 X→S 降级命令，或提供可切换的公平策略（严格 FIFO 与写者优先）。

## 解决思路
- 核心数据结构
  - 事务表 TxTable：记录状态（活跃/中止/提交）、优先级、持有的锁集合、等待中的请求与其开始等待时间。
  - 资源表 ResTable：每个资源维护
    - 当前持有者列表（S 可多，X 最多 1）
    - 等待队列（元素包含：txId、mode、是否升级、入队时间、超时设置）
  - 等待图 WFG：邻接表，边 A→B 表示 A 被 B 阻塞（来自直接冲突或升级等待）。
- 授予与队列规则
  - 尝试授予时：
    - 若队首是写者/升级，且兼容当前持有者则授予；否则停止。
    - 若队首是读者，批量处理连续读者，直到遇到写者/升级或与持有者冲突。
  - 新读者到达时：若等待队列为空且当前持有者无冲突且队首不是写者/升级，则立即授予；否则入队输出 QUEUED。
  - 升级：若已持有 S，生成升级请求，插入队首并标记 UPGRADE；其阻塞集为“除了自己之外的全部当前持有 S 的事务”。
- 死锁检测
  - 在状态变化后重建或增量更新等待图。
  - 运行环检测（DFS/Tarjan/Kahn 任一）。若存在环，依据策略选择牺牲者，输出 DEADLOCK 和 ABORT，释放其全部锁并清理其等待项，然后再次尝试授予。
- 超时处理
  - TICK 推进逻辑时钟；遍历等待请求，若 now - waitStart > timeout，则输出 TIMEOUT 并 ABORT 整个事务；释放后重新尝试授予。
- 事件顺序与输出
  - 每条输入命令处理时：
    1) 执行直接动作并输出（GRANTED/QUEUED/BLOCKED/RELEASED 等）。
    2) 进行死锁检测与可能的中止、授予，依次输出。
    3) 若为 TICK，推进时间并输出 TICK now，再处理可能的超时与后续授予。
- 实现建议
  - 使用哈希表存 Tx 与 Res 的快速定位；等待队列用双端队列。
  - BLOCKED 的阻塞者集合按事务 ID 排序输出，确保确定性。
  - 牺牲者选择严格按优先级→持锁数→事务 ID 字典序进行。
  - 注意升级请求与普通写者的相对优先级（升级在队首）。

该问题覆盖了并发控制核心要点：锁兼容性、队列公平性、升级/降级语义、等待图与死锁检测、超时与恢复策略。实现中可使用多线程或事件驱动，但需保证语义正确与输出可复现。

## 问题标题
可删除的前缀字典与限量自动补全

## 问题描述
实现一个支持动态更新的前缀字典，维护一组仅包含小写字母的单词（不含重复）。需要支持三类操作：
- 添加单词
- 删除单词
- 基于给定前缀查询最多 K 个按字典序排列的候选词（自动补全）

查询时，如果以该前缀开头的单词数不足 K 个，则返回能找到的全部；如果一个也没有，输出一个连字符“-”。

本题旨在考察对字符串数据结构（如 Trie/前缀树，或基于有序集合的范围查询）的设计与实现能力，以及在高并发操作下的时间与空间效率权衡。

## 技术要求
- 输入包含多条指令，需在线处理（每条指令立刻生效）。
- 字典语义为集合：相同单词多次添加等价于一次；删除不存在的单词应安全忽略。
- 词汇仅由小写字母 a-z 构成，长度在 1 到 30 之间。
- 查询返回按字典序升序的至多 K 个候选词，同一行以空格分隔；若无候选则输出“-”。
- 性能目标（建议，不作硬性判定）：  
  - ADD/DEL 平均时间 O(L)，L 为单词长度  
  - QUERY 平均时间 O(P + R)，P 为前缀长度，R 与输出规模成正比（可视为 K 乘以平均单词长度的常数倍）
- 允许语言：任意主流编程语言（Python/Java/JavaScript/C++/Go 等）。
- 可使用的核心数据结构建议：
  - 首选：Trie（前缀树），孩子指针为固定 26 分支或映射。节点需保存：
    - 子链接
    - 是否为单词结尾
    - 通过该节点的单词计数（用于删除时回收/剪枝）
  - 备选：若语言原生提供有序集合（如 C++ std::set / std::map，Java TreeSet/TreeMap），可用“前缀范围”迭代实现 QUERY（lower_bound(prefix) 遍历至 prefix 的上界）。
- 禁止在每次 QUERY 时对全集合再排序（会超时）。

## 输入输出示例
输入格式：
- 第一行：整数 Q（操作数）
- 接下来 Q 行每行一条指令，指令有三类：
  - ADD word
  - DEL word
  - QUERY prefix K

输出格式：
- 对于每条 QUERY 指令，输出一行结果：空格分隔的单词列表，或单独一个字符“-”。

示例输入：
10
ADD apple
ADD app
ADD application
ADD apt
QUERY ap 3
DEL app
QUERY ap 3
ADD apron
QUERY ap 5
QUERY b 3

示例输出：
app apple application
apple application apt
apple application apron apt
-

说明：
- 第一次查询返回以“ap”开头的前三个词，按字典序为 app, apple, application
- 删除 app 后，再查前三个为 apple, application, apt
- 添加 apron 后，再查最多 5 个为 apple, application, apron, apt（共 4 个）
- 查询以 b 开头时不存在，输出“-”

## 测试用例
测试用例1：基本操作与重复插入/删除
输入：
14
ADD cat
ADD car
ADD cart
ADD car
QUERY ca 5
DEL car
QUERY ca 5
DEL car
DEL dog
QUERY c 2
ADD dog
QUERY d 3
DEL dog
QUERY d 1

输出：
car cart cat
cart cat
cart cat
dog
-

测试用例2：边界与前缀等于单词
输入：
12
ADD a
ADD ab
ADD abc
ADD abcd
QUERY a 10
QUERY ab 2
DEL ab
QUERY ab 3
DEL a
QUERY a 2
DEL abc
QUERY ab 5

输出：
a ab abc abcd
ab abc
abc abcd
abc abcd
abcd

测试用例3：无结果与K为1
输入：
8
ADD hello
ADD help
QUERY hi 3
QUERY h 1
DEL hello
QUERY h 1
DEL help
QUERY h 1

输出：
-
hello
help
-

测试用例4：大K与顺序校验
输入：
9
ADD beta
ADD bet
ADD better
ADD between
ADD be
QUERY be 10
DEL bet
QUERY be 10
QUERY bet 10

输出：
be bet beta better between
be beta better between
beta better between

## 评分标准
- 正确性（70分）
  - 集合语义正确处理重复 ADD/DEL（10分）
  - QUERY 仅返回当前存在的单词，字典序正确（20分）
  - 空结果输出“-”（5分）
  - 删除后数据结构一致性（防止“幽灵词”）（15分）
  - 前缀即完整单词与其扩展词同时存在时的正确性（10分）
  - 边界情况处理（空前缀不允许、K≥1、词长范围）（10分）
- 性能与实现（20分）
  - 操作复杂度与内存控制合理，避免全量排序/线性扫描全集（10分）
  - 查询时基于前缀节点的受限 DFS/迭代，能提前剪枝（10分）
- 代码质量（10分）
  - 结构清晰、适当封装、命名规范、注释说明关键逻辑（10分）

## 解决思路
- 数据结构选择
  - Trie（推荐）
    - 每个节点包含：
      - children[26] 或 Map<Character, Node>
      - isWord 布尔标记
      - passCount（通过该节点的单词数量，用于删除时回收和查询时快速判断是否有必要继续）
    - 插入（ADD）
      - 沿路径创建缺失节点，passCount++，尾节点标记 isWord=true
      - 若单词已存在（尾节点 isWord 已为 true），则不重复计数
    - 删除（DEL）
      - 若单词不存在直接返回
      - 沿路径 passCount--，当子节点 passCount 归零时可释放该子树（优化内存，非必须）
      - 尾节点 isWord=false
    - 查询（QUERY）
      - 先走到前缀节点，若不存在直接输出“-”
      - 从该节点起按字母 a→z 做受限 DFS/迭代，遇到 isWord 则收集，直到收集到 K 个或子树耗尽
      - 用 StringBuilder/数组维护当前路径，避免重复字符串拼接带来的高开销
  - 有序集合（备选，依赖语言特性）
    - 将所有单词保存在 TreeSet/ordered set
    - 对 prefix，计算下界 lower_bound(prefix) 与上界 bound= prefixWithNext(prefix)（如将最后一位+1或 prefix + '{'）
    - 从下界起迭代最多 K 个、且严格小于上界的元素
    - 插入/删除 O(log N)，查询 O(log N + K)
- 关键边界与注意点
  - 同一单词重复 ADD 不应改变结构（可通过尾节点 isWord 判断）
  - 删除不存在的词不应抛出异常，不改变结构
  - 查询时要确保严格以 prefix 开头；使用 Trie 时自然满足；使用有序集合时需检查上界
  - K 可能大于可用词数，确保不越界且按实际数量返回
  - 字典序需与字符集一致（仅 a-z，'a' < ... < 'z'）
- 复杂度分析（Trie 方案）
  - ADD/DEL：O(L)
  - QUERY：O(P + min(K, M) * avgWordLenInSubtree)，通常可视为 O(P + 输出规模)
  - 空间：O(Σ L)，Σ为当前字典中单词的总长度，常数与分支度有关（26）

提示：若使用 Python，建议用数组表示 26 个孩子并用整数索引映射字符；DFS 时避免深层递归（可改用显式栈）以防极端情况下的递归深度问题。