Problem1214--#6255. 「CodePlus 2017 12 月赛」化学狂暴

1214: #6255. 「CodePlus 2017 12 月赛」化学狂暴

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

在那遥远的钦钦草原,住着Yazid和YJQQQAQ,他们都是炼金术士。

一般而言,题目背景总是没有用的,但这道题是个例外。在这里,我们将严谨地介绍钦钦草原世界化学学科的一些基本知识。如果你对这些内容感到枯燥乏味,你也可以跳过这个部分,直接阅读题目描述中的简述并结合样例来帮助你更快地理解题目。

钦钦草原的世界里共有262626元素,分别用大写字母AZ表示。

钦钦草原世界中的物质由元素构成,对于任意的物质,每种元素的出现次数都是非负整数,且至少有111种物质的出现次数为正整数,我们把每种元素在物质中的出现次数称作该元素在该物质中的下标。我们可以按AZ的顺序写下每种元素及其下标来描述一个物质。这是一个例子:A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0。这个例子描述了一种JQ各出现111次,Y出现222次的物质。

然而,这种描述方法实在是太麻烦了,于是钦钦草原世界中的炼金术士们便尝试简化物质的描述。对于某种物质,我们定义“虚无元素”表示在该物质中下标为000的元素,“单一元素”表示在该物质中下标为111的元素。针对这两个定义,炼金术士们提出了两种化简方式:

  • 省略“虚无元素”:将“虚无元素”的字母和下标省略。如上面的物质可以通过该操作化简为:J1Q1Y2
  • 省略“单一元素”的下标:将“单一元素”的下标省略。如上面的物质可以通过该操作化简为:A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0

特别地,对于同时省略了“虚无元素”和“单一元素”下标的表示,我们把它叫做该物质的“最简式”。如上面物质的“最简式”即为:JQY2

由于钦钦草原世界的化学研究仍处于起步阶段,因此对于任意的物质,所有元素下标均为不超过999的非负整数。

化学方程式是描述化学反应的式子。一个化学方程式包含恰好一个等号(=),等号两边是由加号(+)连接的若干物质。形象地说,它的形式是这样的:

物质+物质+…+物质=物质+物质+…+物质

除了需要满足上述格式外,元素守恒也是不可忽视的。这表示等号两边所有元素在各物质中的出现次数总和必须相等。比如,这就是一个合法的(格式正确、元素守恒的)化学方程式:

JQY2+J2=J3QY2

需要特别注意的是,在化学方程式的书写中,未被化至“最简式”的元素也是可以被接受的。例如,下面的化学方程式也是合法的:

J1Q1Y2+J2=J3Q1Y2

而下面这个化学方程式就不是合法的了,因为它并没有满足元素守恒。

JQY2+J2=JQY

钦钦草原化学学科的基本知识就介绍到这。祝各位选手武运昌隆!


所谓化学方程式,即是用加号(+)和等号(=)连接一些化学物质的式子。保证一个化学方程式中含有恰好一个等号(=)。化学物质由一些元素(用大写字母AZ表示)加上下标(保证下标为不超过999的非负整数)连接而成的。例如:JQY2A0J1QY2等。书写时需要保证字典序越小的字母排在越前面。

需要注意的是,像A0J1QY2这样的物质书写同样是合法的,虽然事实上它和JQY2是等价的。我们把下标为111的元素称为“单一元素”,把下标为000的元素称为“虚无元素”。在书写一种物质时,我们既可以省去“单一元素”的下标,又可以直接省去“虚无元素”。特别地,我们把用这两种规则省略至最简的书写称为该物质的“最简式”。例如,JQY2就是A0J1Q1Y2的最简式。

既然称之为“方程式”,元素守恒就是必须的了。对于一个化学方程式,元素守恒指的是指等号两边所有元素的下标之和相等。比如,这个化学方程式就是元素守恒的:

JQY2+J2=J3QY2

而这个化学方程式就是不合法的,因为它不满足元素守恒:

JQY2+J2=JQY

作为一名资深炼金术士,Yazid自然是整日沉迷在化学狂暴中。某一天,Yazid写下了nnn个化学方程式,并把它们放在一边,为后续的研究做着准备。

然而,见习炼金术士YJQQQAQ不慎打翻了一瓶绿色的试剂,导致Yazid写下的所有化学方程式中,都有恰好111个物质被绿色液体弄得模糊不清了。

暴怒的Yazid狠狠地把YJQQQAQ批判了一番,并要求他将所有模糊不清的物质重新写出来。除此之外,作为惩罚,无论原来Yazid如何书写这些物质,YJQQQAQ都必须将它们以“最简式”的形式写出

如果不能完成这些任务,Yazid就会把他从钦钦草原放逐。面对这么多的化学方程式,弱小、无助的YJQQQAQ手足无措,于是他找到了钦钦草原最擅长编程的你,请你帮他完成任务。

输入格式

从标准输入读入数据。

第一行222个整数n,mn,mn,m,分别表示化学方程式的数目和Yazid的书写习惯。其中,书写习惯mmm000333之间的整数,对于不同的mmm,Yazid书写物质的方式不同(这一信息可能对你解决部分测试点有帮助):

  • 如果m=0m=0m=0,则Yazid在书写方程式时一定将所有物质化为“最简式”;
  • 如果m=1m=1m=1,则Yazid在书写方程式时一定将所有物质的“虚无元素”省略,且不会存在“单一元素”的下标被省略;
  • 如果m=2m=2m=2,则Yazid在书写方程式时一定将所有物质“单一元素”的下标省略,且不会存在“虚无元素”被省略;
  • 如果m=3m=3m=3,则Yazid在书写方程式时一定不会省略“单一元素”的下标,也一定不会省略“虚无元素”。

接下来nnn行,每行一个字符串,描述一个被污染的化学方程式。其中,被污染的物质用?表示,保证对于每一个方程式都会存在恰好111?

数据保证化学方程式严格按照题目背景题目描述中的格式,且不存在多余的空格或其他字符。

输出格式

输出到标准输出。

输出nnn行,每行一个字符串,表示化为“最简式”的?所表示的物质。特别地,对于无解的情况(即?表示的物质超出钦钦草原世界化学学科的研究范围),请输出"No Solution"(不含引号)。

样例

样例1输入
3 0
A=?
?=A+B
C+O2=?
样例1输出
A
AB
CO2
样例2输入
3 1
A1=?
A1+?=B1
C1+O2=?
样例2输出
A
No Solution
CO2
样例3输入
1 2
A0B0C0D0E0F0G0H0I0JK0L0M0N0O0P0QR0S0T0U0V0W0X0Y2Z0=?
样例3输出
JQY2
样例4输入
2 3
?=A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0
A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0+A0B0C0D0E0F0G0H0I0J1K0L0M0N0O0P0Q1R0S0T0U0V0W0X0Y2Z0=?
样例4输出
JQY2
J2Q2Y4

数据范围与提示

测试点编号m?在方程式的最左端等号左边不含+等号右边不含+
1000 YesYesYes
2111
3222
4333
5000 YesYes
6111
7222
8333
9000 Yes Yes
10111
11222
12333
13000 Yes
14111
15222
16333
17000
18111
19222
20333

如表格中“?在方程式的最左端”为Yes,则表示该测试点保证每个字符串的第一个字符均为?;否则无特殊保证。

如表格中“等号左边+”为Yes,则表示该测试点保证等号左边没有加号(+),即等号左边只有一种物质;否则无特殊保证。

如表格中“等号右边+”为Yes,则表示该测试点保证等号右边没有加号(+),即等号右边只有一种物质;否则无特殊保证。

对于所有的测试点,保证n≤100n\leq 100n100,保证每个方程式中等式两边的加号+都不超过555个,这也意味着每行字符串(每个化学方程式)的长度不超过635635635


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/王聿中 命题/王聿中 验题/陈宇
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。

Source/Category