日志由 n 条记录组成,每条记录是字符 A 或 B。初始时两个计数器 C1,C2 的值均为 0。读取日志时,若遇到 A,则将 C1 增加 1;若遇到 B,则将 C2 增加 1。现在需要判断:是否存在某个前缀(包括最开始),使得 C1=X 且 C2=Y。若存在则可能不矛盾,输出 ac;否则一定矛盾,输出 wrong。
核心转化: “中途出现过 X,Y” ⇔ “存在某个前缀的
A计数为 X,B计数为 Y”。
因此只需一次线性扫描,维护两种前缀计数并判断是否命中。
小蓝拿到了一份操作日志。日志由 n 条记录组成,每条记录是字符 R 或 W。初始时,两个计数器 C1,C2 的值均为 0。读取日志时,若遇到 R,则将 C1 增加 1;若遇到 W,则将 C2 增加 1。
现在有人告诉小蓝,在某个时刻(包括最开始),两个计数器的值恰好同时为 X 和 Y。请你判断日志是否一定与这个信息矛盾。如果日志中存在一个前缀(包括空前缀,即开始前)使得 C1=X 且 C2=Y,则可能不矛盾;否则一定矛盾。
输入包含多组测试数据,需要你作出判断:如果一定矛盾,输出 wrong;否则输出 ac。
约束条件
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册