汉诺塔
Description
有三个立柱A、B、C。A柱上穿有大小不等的圆盘N个，较大的圆盘在下，较小的圆盘在上。要求把A柱上的圆盘全部移到C柱上，保持大盘在下、小盘在上的规律（可借助B柱）。每次移动只能把一个柱子最上面的圆盘移到另一个柱子的最上面。请输出移动过程。
Input
输入描述：
输入一个整数n
Output
输出描述：
输出移动过程
Sample Input 1
3
Sample Output 1
a->c
a->b
c->b
a->c
b->a
b->c
a->c
def mov(n, a='a', b='b', c='c'):
# 将n个盘从a柱借助b柱移动到c柱
if n == 0: # n==0则无需操作
return
mov(n-1, a, c, b) # 将a柱上n-1个小盘挪到b柱
print(a + '->' + c) # 将a柱剩下的大盘挪到c柱
mov(n-1, b, a, c) # 将b柱上n-1个小盘挪到c柱
n = int(input())
mov(n)
3
a->c
a->b
c->b
a->c
b->a
b->c
a->c
# 汉诺塔字符画面展示
# 声明N
N = 0
step = 0
def print_screen(n, dict_post):
scr = []
scr.append('-'*(3*(2*n+1+1)+1))
scr.append(' '*(n+1)+'A'+' '*(2*n+1)+'B'+' '*(2*n+1)+'C'+' '*(n+1))
scr.append('-'*(3*(2*n+1+1)+1)) # 底座
for i in range(n):
s = ' '
for x in 'ABC':
p = dict_post[x][i] if i < len(dict_post[x]) else 0
s += ' '*(n-p) + '='*p + '|' + '='*p + ' '*(n-p) + ' '
scr.append(s)
scr.append(' '*(n+1) + '|' + ' '*(2*n+1) + '|' + ' '*(2*n+1) + '|' + ' '*(n+1)) # 额外露出的柱子
for i in range(-1, -len(scr)-1, -1):
print(scr[i])
print()
def mov(n, dict_post, a='A', b='B', c='C'):
if n == 0:
return
mov(n-1, dict_post, a, c, b)
global step
step += 1
print('step ' + str(step) + ': ' + a + '->' + c)
dict_post[c].append(dict_post[a].pop())
print_screen(N, dict_post)
mov(n-1, dict_post, b, a, c)
while N <= 0:
N = int(input('输入正整数N：'))
stka = [x for x in range(N, 0, -1)]
stkb = []
stkc = []
dict_post = {
'A': stka,
'B': stkb,
'C': stkc
}
print_screen(N, dict_post)
mov(N, dict_post)
输入正整数N：3
| | |
=|= | |
==|== | |
===|=== | |
-------------------------
A B C
-------------------------
step 1: A->C
| | |
| | |
==|== | |
===|=== | =|=
-------------------------
A B C
-------------------------
step 2: A->B
| | |
| | |
| | |
===|=== ==|== =|=
-------------------------
A B C
-------------------------
step 3: C->B
| | |
| | |
| =|= |
===|=== ==|== |
-------------------------
A B C
-------------------------
step 4: A->C
| | |
| | |
| =|= |
| ==|== ===|===
-------------------------
A B C
-------------------------
step 5: B->A
| | |
| | |
| | |
=|= ==|== ===|===
-------------------------
A B C
-------------------------
step 6: B->C
| | |
| | |
| | ==|==
=|= | ===|===
-------------------------
A B C
-------------------------
step 7: A->C
| | |
| | =|=
| | ==|==
| | ===|===
-------------------------
A B C
-------------------------
交换数值
Description
将整数a、b的值进行交换，并且不使用任何中间变量。
Input
输入描述：
输入待处理的两个整数 a 和b
Output
输出描述：
a 和b 的值交换
Sample Input 1
a=100
b=200
Sample Output 1
a=200
b=100
a = int(input().split('=')[1])
b = int(input().split('=')[1])
a, b = b, a
print('a=%d\nb=%d' % (a, b))
a=100
b=200
a=200
b=100
员工排序
Description
某公司要针对员工情况统一调薪，现有一个员工列表，包含姓名、职级、工作年限、工资信息。现要求将该列表按以下规则重新排序：
1、职级高的排在前面
2、若职级相同，按工资少的排前面
3、若工资相同，工作年限长的排前面
Input
第一行输入一个整数n，表示员工列表中员工的人数
接下来的n行，分别输入员工的姓名、职级、工作年限和工资信息，各项信息用空格分隔
Output
输出按要求重新排列的员工列表，每名员工信息（姓名、职级、工作年限和工资）占一行
Sample Input 1
6
张三 3 3 3000
李四 3 4 3000
王五 3 3 4000
赵六 4 3 3000
陆奇 4 4 4000
闫八 4 4 3980.99
Sample Output 1
赵六 4 3 3000.00
闫八 4 4 3980.99
陆奇 4 4 4000.00
李四 3 4 3000.00
张三 3 3 3000.00
王五 3 3 4000.00
n = int(input())
staff = []
for i in range(n):
person = {}
msg = input().split()
person['name'] = msg[0] # 姓名
person['level'] = int(msg[1]) # 职级
person['years'] = int(msg[2]) # 年限
person['salary'] = float(msg[3]) # 工资
staff.append(person)
# 按三个关键字排序：职级从高到低，工资从低到高，工作年限从高到低
# 由于这三个关键字都是数字类型，所以可以借助负号利用sort默认的从小到大排序性质，实现从高到低的排序逻辑
staff.sort(key=lambda x:(-x['level'], x['salary'], -x['years']))
for person in staff:
# 根据样例输出，工资应保留小数点后两位
print('%s %d %d %.2f' % (person['name'], person['level'], person['years'], person['salary']))
6
张三 3 3 3000
李四 3 4 3000
王五 3 3 4000
赵六 4 3 3000
陆奇 4 4 4000
闫八 4 4 3980.99
赵六 4 3 3000.00
闫八 4 4 3980.99
陆奇 4 4 4000.00
李四 3 4 3000.00
张三 3 3 3000.00
王五 3 3 4000.00
字符串查找和比较(pass)
Description
写函数实现如下功能，给定字符串A和B,输出A和B中的最长公共子串。比如A="aocdfe" B="pmcdfa" 则输出"cdf"。
Input
输入待处理的两个字符串 str1，str2
Output
找出两个字符串最长的公共子串
Sample Input 1
aocdfe
pmcdfa
Sample Output 1
cdf
s1 = input()
s2 = input()
if len(s1) < len(s2): # 截取操作较短的字符串，提高效率
s1, s2 = s2, s1
ans = ''
for _len in range(1, len(s2)+1): # 枚举子串长度
for _start in range(len(s2)-_len+1): # 枚举子串起始位置
_str = s2[_start:_start+_len-1] # 子串
if s1.find(_str) >= 0: # find找不到子串返回-1，否则返回子串起始位置
ans = ans if len(ans) > len(_str) else _str # 比较保存较长子串
print(ans)
aocdfe
pmcdfa
cdf
进程排序(pass)
Description
某系统中有n个进程，每个进程都有自己唯一的进程id（PID），同时每个进程最多还有一个父进程，父进程id为（PPID），和一个或多个子进程。
若某进程没有父进程，则PPID为0。 当某一进程被终止时，其子进程也将被终止。
现给出进程id列表和起对应的父进程id列表，当要终止某一进程时，计算最终会终止哪些进程，并将要终止的PID按升序排列。
Input
第一行输入两个整数n和k，n表示当前系统中运行的进程数；k表示要终止进程的PID
第二行输入n个正整数，表示进程列表，每个整数表示进程的PID
第三行输入n个正整数，表示进程列表中的进程对应的父进程PPID列表。
Output
输出当进程k终止时，所有会被终止的进程PID，并按PID升序排列，每个PID用空格分隔。
Sample Input 1
4 5
1 3 10 5
3 0 5 3
Sample Output 1
5 10
# n, k = map(int, input().split())
# pid_l = list(map(int, input().split()))
# ppid_l = list(map(int, input().split()))
n, k = input().split()
pid_l = input().split()
ppid_l = input().split()
q = [k] # 待kill队列
ans = list()
while len(q) > 0: # 运行至队列为空
f = q.pop() # kill进程
ans.append(f)
for i in range(len(ppid_l)): # 寻找刚kill进程的子进程
if ppid_l[i] == f:
q.append(pid_l[i])
ans.sort(key=lambda x: int(x)) # 保存的是字符串列表，排序关键字需要转int，否则是按字符串字典序排序
# for i in range(len(ans)): # 不优雅的插空格
# print('' if i == 0 else ' ', ans[i], sep='', end='')
print(' '.join(ans)) # python优雅的插空格写法
4 5
1 3 10 5
3 0 5 3
5 10
罗马数字
Description
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I， 1
V， 5
X， 10
L， 50
C， 100
D， 500
M， 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
Input
罗马数字
Output
转换后的整数
Sample Input 1
III
Sample Output 1
3
dict_num = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
def calc(str):
# 观察可知罗马数字转阿拉伯数字的规律：
# 1. 从左往右找到第一个代表数字最大的字母，设位置为max_i
# 2. 找到p_max右侧所有代表数字与max_i位置相同的字母，包括max_i位置的所有字母代表数字之和为当前罗马数字的基础值
# 3. 递归计算刚刚找到的“基础值”子串左侧的罗马数字和右侧的罗马数字
# 4. 当前数字的基础值减去左侧的结果并加上右侧的结果，即为当前罗马数字的转换结果
if len(str) == 0:
return 0
max_i = 0
for i in range(len(str)): # step 1
if dict_num[str[i]] > dict_num[str[max_i]]:
max_i = i
cnt = 1
for i in range(max_i+1, len(str)): # step 2
if dict_num[str[i]] == dict_num[str[max_i]]:
cnt += 1
elif dict_num[str[i]] < dict_num[str[max_i]]:
break
ans = cnt * dict_num[str[max_i]] - calc(str[:max_i]) + calc(str[max_i+cnt:]) # step 3,4
return ans
s = input()
print(calc(s))
XLV
45
尼姆博弈
Description
你和你的朋友，两个人一起玩 Nim 游戏：
桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
Input
整数n
Output
true或false
Sample Input 1
4
Sample Output 1
false
# n = int(input().strip())
# print('true' if n % 4 != 0 else 'false')
# 本题即求该nim游戏是否先手必胜，以下分情况讨论：
# 1. n<4时，先手可以一次取走所有石子，所以必胜
# 2. n==4时，无论先手取1~3的多少颗，后手都可以取走剩下的石子，所以后手必胜
# 3. n==4k（k为整数且k>=1），无论先手如何取石子，比如m颗（1<=m<=3），后手只需取(4-m)颗即可，保证后手可以取到最后一颗石子，所以后手必胜
# 3. n==4k+1（k>=1）时，先手只需取走1颗石子，
# 然后无论后手如何取石子，比如m颗（1<=m<=3），先手只需取(4-m)颗即可，保证先手可以取到最后一颗石子，所以先手必胜
# 4. n==4k+s（k>=1, 1<=s<=3），先手只需取走s颗石子，
# 然后无论后手如何取石子，比如m颗（1<=m<=3），先手只需取(4-m)颗即可，保证先手可以取到最后一颗石子，所以先手必胜
# 综上，当n为4的倍数时，后手必胜，否则先手必胜
print('true' if int(input().strip()) % 4 != 0 else 'false')
100
false
丑数
Description
给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。(1通常被视为丑数)
Input
整数n
Output
true或false
Sample Input 1
6
Sample Output 1
true
n = int(input())
while n % 2 == 0:
n //= 2 # 这里不能使用'/'，因为商默认为float类型，使用整除'//'可以达到想要的效果
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
print('true' if n == 1 else 'false') # n最后结果为1说明：1. n==1; 2. n的因数只包含2、3、5
89
false
股票报价
Description
给定某股票每日的报价和一个目标值，请在所有报价中找出和为目标值的那两天的报价，并打印出对应的报价。
假设每种输入只会对应一个答案，且每日的报价不会重复。
你需要按报价从小到大的顺序打印答案。
Input
第一行是某股票每日的报价，这些报价是正整数且用空格相隔，例如：17 20 33
Output
37
Sample Input 1
17 20 33
37
Sample Output 1
17 20
prices = list(map(int, input().split()))
p_sum = int(input().strip())
for i in range(len(prices)):
for j in range(i+1, len(prices)):
if prices[i]+prices[j] == p_sum: # 枚举两个报价然后计算是否满足条件即可
if prices[i] < prices[j]: # 先输出较小值
print(prices[i], prices[j])
else:
print(prices[j], prices[i])
break
17 20 33
37
17 20
批阅奏章
Description
某朝皇帝有大臣n名（1<=n<=1000），分别编号大臣1~n。某日皇帝身体抱恙，奏章堆积如山无法及时一一批阅，便命身旁內侍帮他把奏章按指定顺序排序后再阅。于是皇帝亲自挑选了几个值得信赖的重臣并排好序，要求把他们的奏章按排好的顺序放到前面，其他的按照编号升序排列即可。现在要求你写一个程序来帮皇上解决这个问题，即已知奏章总数和顺序、钦点重臣的排列顺序，求得皇帝查阅奏章的顺序。
Input
第一行输入两个整数p（1<=p<=5000）和q，其中p表示堆积奏章的总数、q表示皇帝钦点重臣数
第二行输入p个数，表示所有按呈递顺序递上来的奏章来自于哪个大臣（大臣编号）
第三行输入q个数，表示皇帝钦点并排好序的重臣编号
Output
输出奏章按指定顺序排好序后，皇帝按大臣编号批阅的顺序
Sample Input 1
5 3
5 4 3 2 1
3 5 4
Sample Output 1
3 5 4 1 2
p, q = input().split()
p_l = input().split()
q_l = input().split()
p_l = list(set(p_l)-set(q_l)) # 利用差集，从所有奏折中排除重臣奏折
p_l.sort(key=lambda x: int(x)) # 对非重臣奏折按编号从小到大排序
q_l.extend(p_l) # 将排序后非重臣奏折接到重臣奏折后
print(' '.join(q_l))
5 3
5 4 3 2 1
3 5 4
3 5 4 1 2
水仙花数
Description
如果一个 3 位数等于其各位数字的立方和，则称这个数为水仙花数。
例如：153 = 1^3 + 5^3 + 3^3，因此 153 就是一个水仙花数
Input
输入一个整数a与一个整数b, 用空格分隔
Output
输出a到b区间内的水仙花数
Sample Input 1
100 170
Sample Output 1
153
a, b = map(int, input().split())
for i in range(a, b+1):
# 1. 使用list将转换为str类型的数字拆成包含单个字符字符串的列表，即各位数字的列表
# 2. 使用map将字符映射到数字对应的立方值
# 3. 对刚刚映射的结果求和，判断是否满足水仙花数条件
if i == sum(map(lambda x: int(x)**3, list(str(i)))):
print(i)
100 170
153
校验和
Description
校验和是一种扫描数据包并返回单个数字的算法，其思想是，如果数据包发生更改，校验和也会发生更改，因此校验和通常用于检测传输错误，验证文档内容，以及在许多其他需要检测数据中不需要的更改的情况下。对于这个问题，您将实现一个名为“加速”的校验和算法。“加速”数据包只允许使用大写字母和空格。它总是以大写字母开头和结尾。否则，空格和字母可以以任何组合出现，包括连续空格。“加速”是每个字符在数据包中的位置乘以字符值的乘积之和。空格的值为零，而字母的值等于其在字母表中的位置。因此，A=1，B=2，等等，直到Z=26。
Input
输入由一个或多个数据包组成，后面是一行，其中只包含#，表示输入结束。每个数据包本省在一行上，不以空格开头或结尾，包含1到255个字符。
Output
对于每个数据包，在输出中的单独一行输出其结果。
Sample Input 1
SASDF#
Sample Output 1
124
flag = 1
while flag == 1:
s = input().strip()
# if s == '#': # 若'#'单独成行，应使用本处控制循环
# break
ans = 0
for i in range(len(s)):
if s[i] == '#': # 根据样例，'#'可能跟在某组结果的结尾
flag = 0
break
ans += (i+1)*(0 if s[i] == ' ' else ord(s[i])-64) # 根据题意，利用A~Z的ASCII码值连续的性质计算结果
print(ans)
SASDF#
124
万圣节
Description
今天是万圣节！农夫约翰带着奶牛去参加化妆舞会，但不幸的是，他只有一套化装服，这套服装正好合适两头长度为S（1≤S≤1000000），农夫约翰有N头奶牛（2≤N≤2000000）为了方便，变化为1……N，母牛i号的长度li是（1≤li≤1000000），如果两头母牛的长度之和不超过服装的长度，那么他们就可以穿上服装，农夫约翰想知道有多少对两头不同的母牛能穿上这套服装。
Input
第一行包括两个空格分隔的整数：N和S，下面n行是每头奶牛的长度li
Output
输出一个整数，表示FJ可以选择的成对奶牛的数量。请注意，两头母牛的顺序并不重要。
Sample Input 1
4 2
2
1
3
1
Sample Output 1
1
n, s = map(int, input().split())
l = list()
for i in range(n):
l.append(int(input()))
ans = 0
for i in range(n):
for j in range(i+1, n):
if l[i]+l[j] <= s: # 枚举两头奶牛，计算是否符合条件
ans += 1
print(ans)
5 10
1
2
3
4
5
10