开始: 2026-10-06 00:00:00

【集训04】CSP-J模拟赛1006

结束: 2026-10-07 00:00:00
当前  2026-11-04 11:35:10  类型: IOI  状态: 已经结束 

P1. 括号修复repair
描述

括号机器人小 I 收到了一条由四种括号组成的序列 s:`<>`、`{}`、`[]`、`()`。

序列中的括号只有两种身份:**开括号**(`<`、`{`、`[`、`(`)与**闭括号**(`>`、`}`、`]`、`)`)。机器人可以对任意一个括号做一次"替换"操作,但受硬件限制,**开括号只能替换成另一种开括号,闭括号只能替换成另一种闭括号**。例如:`<` 可以替换成 `{`,但不能替换成 `)` 或 `>`。

我们定义**合法括号序列(Regular Bracket Sequence)**如下:

1. 空序列是合法括号序列。

2. 若 s_1、s_2 均为合法括号序列,则 \langle s_1\rangle s_2、\{s_1\}s_2、[s_1]s_2、(s_1)s_2 也是合法括号序列。

例如 `[[(){}]<>]` 是合法括号序列,而 `[)()` 与 `][()()` 不是。

请你求出:最少需要替换多少个括号,才能把 s 变成一个合法括号序列。如果无论如何都无法做到,输出 `Impossible`。

输入

一行一个非空字符串 s,仅由 `<>{}[]()` 这八种字符组成

输出

若无法变成合法括号序列,输出 `Impossible`(注意首字母大写,其余小写)。

否则输出一个整数,表示最少的替换次数。


样例

输入

[<}){}

输出

2

输入

]]

输出

Impossible
提示

样例说明

样例 1:把第 1 个字符 `[` 替换成 `(`、第 2 个字符 `<` 替换成 `{`,得到 `({}){}`,是合法括号序列,共替换 2 次。样例 2:两个闭括号没有任何开括号与它们配对,永远无法修复。

| 20% | 1~5 | 20 | \lvert s\rvert \le 20 | 

| 60% | 6~15 | 40(累计 60) | \lvert s\rvert \le 2000 | 

| 100% | 16~25 | 40(累计 100) | \lvert s\rvert \le 10^6 | 

对于全部数据,保证 1 \le |s| \le 10^6。

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交