M02692: 假币问题
brute force, http://cs101.openjudge.cn/pctbook/M02692/
赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。
输入
第一行有一个数字n，表示有n组测试用例。 对于每组测试用例： 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用up'', down'', 或 ``even''表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。
输出
输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。
样例输入
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even样例输出
K is the counterfeit coin and it is light.来源：East Central North America 1998，计算概论05
2023年9月8日写了一遍穷举方法。
只有一个是假币，因此我们可以考虑让每个都当一次假币，然后假设他是重的还是轻的，验证就可以了。
n = int(input())
def check(coins, case):
for item in case:
left, right, res = item.split()
left_total = sum(coins[i] for i in left)
right_total = sum(coins[i] for i in right)
if left_total == right_total and res != 'even':
return False
elif left_total < right_total and res != 'down':
return False
elif left_total > right_total and res != 'up':
return False
return True
for _ in range(n):
case = [input().strip() for _ in range(3)]
for counterfeit in 'ABCDEFGHIJKL':
found = False
for weight in [-1, 1]:
coins = {coin: 0 for coin in 'ABCDEFGHIJKL'}
coins[counterfeit] = weight
if check(coins, case):
found = True
tag = "light" if weight == -1 else "heavy"
print(f'{counterfeit} is the counterfeit coin and it is {tag}.')
break
if found:
break解题思路：在题目描述中，已经明确保证三次称重后能够确定假币，即输入的三组称量数据有唯一的答案。硬币有三种状态：较重的假币、较轻的假币、真币。由于只有1枚假币，且总共只有12枚银币，因此可以对所有的情况进行枚举。假币可能是任意一枚，有12种情况：且假币可能比真币重，也可能比真币轻，有两种情况。在这全部的24种情况当中，只有一种情况能够符合三组称量数据，这就是所要寻找的答案。
假设用0、-1和1表示真币、较轻币和较重币的重量。分别计算天平左侧与右侧的重量，若下面三个条件中有一个不满足，则说明假设不成立，当前的情况与称量数据矛盾。
（1）如果天平左侧较重，且称量结果为up.
（2）如果天平右侧较重，且称量结果为down.
（3）如果天平左右两侧重量相同，且称量结果为even.
解题思路：可以把银币分类，真币的重量为 0,轻假币为-1，重假币为 1，然后把秤变为条件，依次对所有银币假设为假币，总共有 24种情况，遍历一遍就可以了。如果通过三个秤(条件)，就输出当前的银币。
status = [0]*12
left = ['' for _ in range(3)]
right = ['' for _ in range(3)]
result = ['' for _ in range(3)]
def Balanced():
for j in range(3):
leftW = rightW = 0
for k in range(len(left[j])):
leftW += status[ord(left[j][k]) - ord('A')]
rightW += status[ord(right[j][k]) - ord('A')]
if leftW>rightW and result[j][0]!='u':
return False
if leftW == rightW and result[j][0]!='e':
return False
if leftW<rightW and result[j][0]!='d':
return False
return True
for _ in range(int(input())):
for i in range(3):
left[i], right[i], result[i] = input().split()
for i in range(12):
status[i] = 0
i = 0
for i in range(12):
status[i] = 1
if Balanced():
break
status[i] = -1
if Balanced():
break
status[i] = 0
print('{} is the counterfeit coin and it is {}.'.format( chr(i+ord('A')), \
"heavy" if status[i]>0 else "light"))2020fall-cs101，李逸晨
解题思路：2020fall-cs101，方磊。参考了李逸晨大佬的代码，觉得大佬的思路真的非常清晰而且解法应该是题解中最好的。
对一个轻的假币来说（重的同理），在称量中，只要它在天平左边天平右边就会下降，在天平右边天平右边就会上升，不在天平上天平两边就会平衡。只有轻的假币才会满足这种特性。
如果三个式子都成立，那么这就是假币。
# https://stackabuse.com/any-and-all-in-python-with-examples/
# The method any(iterable) behaves like a series of or operators between
# each element of the iterable we passed.
# The all(iterable) method evaluates like a series of and operators between
# each of the elements in the iterable we passed.
for _ in range(int(input())):
L = [[],[],[]]
for i in range(3):
L[i] = input().split()
for f in 'ABCDEFGHIJKL':
if all((f in i[0] and i[2]=='up') or (f in i[1] and i[2]=='down')
or ( f not in i[0] + i[1] and i[2]=='even') for i in L):
print("{} is the counterfeit coin and it is {}.".format(f,'heavy'))
break
if all((f in i[0] and i[2]=='down') or (f in i[1] and i[2]=='up')
or (f not in i[0]+i[1] and i[2]=='even') for i in L):
print("{} is the counterfeit coin and it is {}.".format(f,'light'))
breaks="ABCDEFGHIJKL"
for _ in range(int(input())):
p=[list(input().split()) for _ in range(3)]
for i in s:
if all((i in j[0] and j[2]=="up") or (i in j[1] and j[2]=="down") or (i not in j[1] and i not in j[0] and j[2]=="even") for j in p):
print(f"{i} is the counterfeit coin and it is heavy.")
break
elif all((i in j[0] and j[2]=="down") or (i in j[1] and j[2]=="up") or (i not in j[1] and i not in j[0] and j[2]=="even") for j in p):
print(f"{i} is the counterfeit coin and it is light.")
break这个题老早就做过了，当时只会if else，但是这里我要推荐一下我的大佬室友（不是我们班的）的超强思路（我认为）： 开两个列表，记录每个硬币被怀疑的次数。如果even那么肯定是正常的，就+-一个很大的数就行了（这里我用的是114514），然后最后输出被怀疑次数最多的呢个硬币并且看看最多的是在qing还是zhong列表里，对应着假币本身的轻重
# 室友是大佬，24-工学院
def main():
l= {0:'A',1:'B',2:'C',3:'D',4:'E',5:'F',6:'G',7:'H',8:'I',9:'J',10:'K',11:'L'}
l1= {'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,'K':10,'L':11}
s1=[]
s2=[]
s=[]
qing=[0]*12
zhong=[0]*12
for i in range(3):
shuru=input().split()
s1.append(shuru[0])
s2.append(shuru[1])
s.append(shuru[2])
for i in range(3):
if s[i]=='even':
for j in s1[i]:
qing[l1[j]]=-114514
zhong[l1[j]] = -114514
for j in s2[i]:
qing[l1[j]] = -114514
zhong[l1[j]] = -114514
for i in range(3):
if s[i]=='up':
for j in s2[i]:
qing[l1[j]]+=1
for j in s1[i]:
zhong[l1[j]]+=1
if s[i]=='down':
for j in s1[i]:
qing[l1[j]]+=1
for j in s2[i]:
zhong[l1[j]]+=1
q=s.count('down')+s.count('up')
for i in range(12):
if qing[i]==q:
print(l[i],' is the counterfeit coin and it is light.',sep='')
break
if zhong[i]==q:
print(l[i], ' is the counterfeit coin and it is heavy.', sep='')
break
n=int(input())
for i in range(n):
main()思路：很久之前做的，分类讨论进行实现即可，可以利用集合的运算以及字典优化过程。（心目中的brute force No.2，第三是装箱，第一是熄灯问题）
# 李承容 物理学院 2400011499
n=int(input())
for _ in range(n):
coins=set("ABCDEFGHIJKL")
dic={}
for i in range(3):
a,b,c=map(str,input().split())
if c=="even":
coins=coins-set(a)-set(b)
elif c=="up":
for i in range(4):
if a[i] in dic:
if dic[a[i]]=="light":
coins-=set(a[i])
else:
dic[a[i]]="heavy"
if b[i] in dic:
if dic[b[i]]=="heavy":
coins-=set(b[i])
else:
dic[b[i]]="light"
coins=coins & (set(a)|set(b))
else:
for i in range(4):
if a[i] in dic:
if dic[a[i]]=="heavy":
coins-=set(a[i])
else:
dic[a[i]]="light"
if b[i] in dic:
if dic[b[i]]=="light":
coins-=set(b[i])
else:
dic[b[i]]="heavy"
coins=coins & (set(a)|set(b))
res="".join(coins)
print(f"{res} is the counterfeit coin and it is {dic[res]}.")思路：假币在不平衡的情况下应该归属于同一边，且其不属于平衡结果中的部分，所以用集和处理
# 王梓航、24物理学院
n = int(input())
for _ in range(n):
d, e, f = set('ABCDEFGHIJKL'), set('ABCDEFGHIJKL'), set()
for j in range(3):
a, b, c = input().split()
if c == 'even':
f = f | set(a + b)
elif c == 'up':
d = d & set(a)
e = e & set(b)
else:
d = d & set(b)
e = e & set(a)
g = d & f
h = e & f
e -= h
d -= g
if d:
s = list(d)[0]
print('{} is the counterfeit coin and it is heavy.'.format(s))
continue
s = list(e)[0]
print('{} is the counterfeit coin and it is light.'.format(s))使用了集合的运算，初始化重（heavy）和轻（light）两个集合，代表所有可能的重假币和轻假币，之后根据条件取交集或者补集，逐渐缩减范围，最后取两个之中的非空集合
# 刘人豪 24物理学院
n = int(input())
s = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'}
for j in range(n):
heavy = s.copy()
light = s.copy()
for _ in range(3):
a = input().split()
if a[2] == 'even':
heavy = heavy - set(a[0]) - set(a[1])
light = light - set(a[0]) - set(a[1])
elif a[2] == 'up':
heavy &= set(a[0])
light &= set(a[1])
elif a[2] == 'down':
heavy &= set(a[1])
light &= set(a[0])
x = str(*(heavy ^ light))
if x in light:
print(f'{x} is the counterfeit coin and it is light.')
else:
print(f'{x} is the counterfeit coin and it is heavy.')思路：之前做过一次，用的是枚举。然后现在又做了一次，感觉大脑中对枚举已经有了天然的恐惧，所以就又想了一个不枚举的方法，与群里面的那位大佬不谋而合了。注意此时不是只要只被怀疑过一遍的硬币就是假币。应该是被怀疑了最多次的硬币是假币。这在直观上很好理解：只有一枚假币，那“证据”最多的肯定“最假”。
# 刘家亦 24物院
n = int(input())
idx = {'up': 1, 'down': -1}
handl = {1:'heavy', 0:'light'}
for _ in range(n):
suspect = [[0, 0, 0] for _ in range(12)] # 0: light, 1: equal, 2: heavy
times = [[0, 0] for _ in range(12)]
for _ in range(3):
left, right, res = input().split()
if res == 'even':
for coin in list(left + right):
suspect[ord(coin) - ord('A')][1] += 1 # 标记为平衡
else:
for coin in list(left):suspect[ord(coin) - ord('A')][1 + idx[res]] += 1 # 根据天平状态标记轻或重
for coin in list(right):suspect[ord(coin) - ord('A')][1 - idx[res]] += 1 # 相反方向标记
for i in range(12):
if suspect[i][1] == 0:
if suspect[i][2] != 0 and suspect[i][0] == 0:
times[i] = [suspect[i][2], 1]
elif suspect[i][0] != 0 and suspect[i][2] == 0:
times[i] = [suspect[i][0], 0]
i = times.index(max(times))
print(f'{chr(ord("A") + i)} is the counterfeit coin and it is {handl[times[i][1]]}.')