2018-08-03Arithmetic36 分钟读完 (大约 5432 个字)

PAT解题记录

题目来自PAT网站的 BasicLevel 题目
本文用来记录个人解答的PAT题目，仅供个人学习使用，未经允许不得转载，以下均为Python3解法

1001 害死人不偿命的(3n+1)猜想 (15)

卡拉兹(Callatz)猜想：
对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？
输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。
输出格式：输出从n计算到1需要的步数。
输入样例：

输出样例：

Solution

def solution(n):
  step = 0
  while n > 1:
    step += 1
    if n % 2 == 0:
      n /= 2
    else:
      n = (3 * n + 1) / 2
  return step

test = int(input())
print(solution(test))

1002 写出这个数 (20)

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。
输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10^100^。
输出格式：在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。
输入样例：

1	1234567890987654321123456789

输出样例：

yi san wu

Solution

def solution(n):
  sum_str = str(sum(map(int, n)))
  table = {'0':'ling', '1':'yi', '2':'er', '3':'san', '4':'si', '5':'wu', '6':'liu', '7':'qi', '8':'ba', '9':'jiu'}
  return ' '.join([table[key] for key in sum_str])

test = input()
print(solution(test))

1004 成绩排名 (20)

读入n名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。
输入格式：每个测试输入包含1个测试用例，格式为:

第1行：正整数n
第2行：第1个学生的姓名 学号 成绩
第3行：第2个学生的姓名 学号 成绩
... ... ...
第n+1行：第n个学生的姓名 学号 成绩

其中姓名和学号均为不超过10个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。
输出格式：对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。
输入样例：

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

输出样例：

1 2	Mike CS991301 Joe Math990112

Solution

def solution(count, grades):
  grades = sorted(grades, key=lambda grade: int(grade[2]), reverse=True)
  print('{} {}'.format(grades[0][0], grades[0][1]))
  print('{} {}'.format(grades[count-1][0], grades[count-1][1]))

count = int(input())
data = []
for i in range(count):
  data.append(input().split(' '))
solution(count, data)

1006 换个格式输出整数 (15)

让我们用字母B来表示“百”、字母S表示“十”，用“12…n”来表示个位数字n（&lt10），换个格式来输出任一个不超过3位的正整数。例如234应该被输出为BBSSS1234，因为它有2个“百”、3个“十”、以及个位的4。
输入格式：每个测试输入包含1个测试用例，给出正整数n（&lt1000）。
输出格式：每个测试用例的输出占一行，用规定的格式输出n。
输入样例1：

输出样例1：

BBSSS1234

输入样例2：

输出样例2：

SS123

Solution

def solution(n):
  nums = list(map(int, n))
  nums = [0] * (3 - len(nums)) + nums
  print('B' * nums[0] + 'S' * nums[1] + ''.join([str(num) for num in range(1, nums[2]+1)]))

test = input()
solution(test)

1009 说反话 (20)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。
输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。
输出格式：每个测试用例的输出占一行，输出倒序后的句子。
输入样例：

1	Hello World Here I Come

输出样例：

1	Come I Here World Hello

Solution

def solution(english):
  return ' '.join(english[::-1])

english = input().split()
print(solution(english))

1010 一元多项式求导（25）

设计函数求一元多项式的导数。（注：xn（n为整数）的一阶导数为nxn−1。）
输入格式:
以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。
输出格式:
以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是表示为 0 0。
输入样例:

1	3 4 -5 2 6 1 -2 0

输出样例:

1	12 3 -10 1 6 0

Solution:

def solution(nums):
    result = []
    for i in range(0, len(nums), 2):
        coe, index = nums[i], nums[i+1]
        if index == 0:
            continue
        result.append('{} {}'.format(coe*index, index-1))
    if not result:
        result.append('0 0')
    return result

nums = list(map(int, input().split()))
print(' '.join(solution(nums)))

1011 A+B和C (15)

给定区间[-2^31, 2^31]内的3个整数A、B和C，请判断A+B是否大于C。
输入格式：
输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。
**输出格式：**
对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。
输入样例：

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例：

Case #1: false
Case #2: true
Case #3: true
Case #4: false

Solution

def solution(abcs):
    for i in range(len(abcs)):
        print('Case #{}: {}'.format(i + 1, str(abcs[i][0] + abcs[i][1] > abcs[i][2]).lower()))

count = int(input())
abcs = []
for i in range(count):
    abcs.append(list(map(int, input().split())))
solution(abcs)

1012 数字分类 (20)

给定一系列正整数，请按要求对数字进行分类，并输出以下5个数字：
A1 = 能被5整除的数字中所有偶数的和；
A2 = 将被5除后余1的数字按给出顺序进行交错求和，即计算n1-n2+n3-n4…；
A3 = 被5除后余2的数字的个数；
A4 = 被5除后余3的数字的平均数，精确到小数点后1位；
A5 = 被5除后余4的数字中最大数字。
输入格式：
每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N，随后给出N个不超过1000的待分类的正整数。数字间以空格分隔。
输出格式：
对给定的N个正整数，按题目要求计算A1~A5并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。
若其中某一类数字不存在，则在相应位置输出“N”。
输入样例1：

1	13 1 2 3 4 5 6 7 8 9 10 20 16 18

输出样例1：

1	30 11 2 9.7 9

输入样例2：

1	8 1 2 4 5 6 7 9 16

输出样例2：

1	N 11 2 N 9

Solution

def solution(nums):
    a1, a2, a3, a4, a5 = 0, 0, 0, [], []
    symbol, flag = 1, False
    for num in nums:
        remainder = num % 5
        if remainder == 0 and num % 2 == 0:
            a1 += num
        elif remainder == 1:
            a2 = a2 + symbol * num
            symbol *= -1
            flag = True
        elif remainder == 2:
            a3 += 1
        elif remainder == 3:
            a4.append(num)
        elif remainder == 4:
            a5.append(num)
    a1 = a1 if a1 > 0 else 'N'
    a2 = a2 if flag > 0 else 'N'
    a3 = a3 if a3 > 0 else 'N'
    a4 = round(sum(a4) / len(a4), 1) if len(a4) > 0 else 'N'
    a5 = max(a5) if len(a5) > 0 else 'N'
    print(a1, a2, a3, a4, a5)


nums = list(map(int, input().split()))
solution(nums[1:])

1017 A除以B（20）

本题要求计算 A/B，其中 A 是不超过 1000 位的正整数，B 是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。
输入格式:
输入在一行中依次给出 A 和 B，中间以 1 空格分隔。
输出格式：
在一行中依次输出 Q 和 R，中间以 1 空格分隔。
输入样例：

1	123456789050987654321 7

输出样例：

1	17636684150141093474 3

Solution:

def solution(a, b):
    q = a // b
    r = a % b
    print(q, r)

a, b = list(map(int, input().split()))
solution(a, b)

1021 个位数统计 (15)

给定一个k位整数N = d~~k-1~~*10^k-1^ + … + d1*10^1^ + d0 (0<=di<=9, i=0,…,k-1, d~~k-1~~>0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定N = 100311，则有2个0，3个1，和1个3。
输入格式：
每个输入包含1个测试用例，即一个不超过1000位的正整数N。
输出格式：
对N中每一种不同的个位数字，以D:M的格式在一行中输出该位数字D及其在N中出现的次数M。要求按D的升序输出。
输入样例：

输出样例：

1
2
3

0:2
1:3
3:1

Solution

import operator
def solution(num):
  result = {}
  num = list(num)
  num.sort()
  for key in num:
    if key in result:
      result[key] += 1
    else:
      result[key] = 1
  for k,v in result.items():
    print('{}:{}'.format(k,v))
test = input()
solution(test)

1023 组个最小数 (20)

给定数字0-9各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意0不能做首位）。例如：给定两个0，两个1，三个5，一个8，我们得到的最小的数就是10015558。
现给定数字，请编写程序输出能够组成的最小的数。
输入格式：
每个输入包含1个测试用例。每个测试用例在一行中给出10个非负整数，顺序表示我们拥有数字0、数字1、……数字9的个数。整数间用一个空格分隔。10个数字的总个数不超过50，且至少拥有1个非0的数字。
输出格式：
在一行中输出能够组成的最小的数。
输入样例：

1	2 2 0 0 0 3 0 0 1 0

输出样例：

10015558

Solution

def solution(counts):
    result = ''
    for i in range(1, 10):
      result += str(i) * counts[i]
    return result[0] + '0' * counts[0] + result[1:]

counts = list(map(int, input().split(' ')))
print(solution(counts))

1031 查验身份证(15)

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：
Z：0 1 2 3 4 5 6 7 8 9 10\ M：1 0 X 9 8 7 6 5 4 3 2
现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。
输入格式：
输入第一行给出正整数N（<= 100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。
输出格式：
按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出“All passed”。
输入样例1：

4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X

输出样例1：

1
2
3

12010X198901011234
110108196711301866
37070419881216001X

输入样例2：

1
2
3

2
320124198808240056
110108196711301862

输出样例2：

1	All passed

Solution

def solution(ids):
  table = {0:'1', 1:'0', 2:'X', 3:'9', 4:'8', 5:'7', 6:'6', 7:'5', 8:'4', 9:'3', 10:'2'}
  weight = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2]
  flag = True
  for id in ids:
    if not id[:17].isdigit():
      print(id)
      flag = False
      continue
    weight_sum = 0
    for i in range(17):
      weight_sum += int(id[i]) * weight[i]
    if table[weight_sum % 11] != id[17]:
      print(id)
      flag = False
  if (flag):
    print('All passed')

count = int(input())
data = [input() for i in range(count)]
solution(data)

1037 在霍格沃茨找零钱（20）

如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut)兑一个西可，很容易。”现在，给定哈利应付的价钱P和他实付的钱A，你的任务是写一个程序来计算他应该被找的零钱。
输入格式：
输入在1行中分别给出P和A，格式为“Galleon.Sickle.Knut”，其间用1个空格分隔。这里Galleon是[0, 10^7^]区间内的整数，Sickle是[0, 17)区间内的整数，Knut是[0, 29)区间内的整数。
输出格式：
在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。
输入样例1：

1	10.16.27 14.1.28

输出样例1：

3.2.1

输入样例2：

1	14.1.28 10.16.27

输出样例2：

-3.2.1

Solution

def solution(p, a):
    # 1*Galleon-->17*Sickle  1*Sickle-->29*Knut
    # Galleon Sickle Knut
    p_knut = p[0] * 17 * 29 + p[1] * 29 + p[2]
    a_knut = a[0] * 17 * 29 + a[1] * 29 + a[2]
    change = a_knut - p_knut
    symbol = 1
    if change < 0:
        change = abs(change)
        symbol = -1
    change_galleon = change // (17 * 29)
    change_sickle = change % (17 * 29) // 29
    change_kunt = change % 29
    print('{}.{}.{}'.format(change_galleon * symbol, change_sickle, change_kunt))

pa = input().split()
p = list(map(int, pa[0].split('.')))
a = list(map(int, pa[1].split('.')))
solution(p, a)

1038 统计同成绩学生(20)

本题要求读入N名学生的成绩，将获得某一给定分数的学生人数输出。
输入格式：
输入在第1行给出不超过10^5^的正整数N，即学生总人数。随后1行给出N名学生的百分制整数成绩，中间以空格分隔。最后1行给出要查询的分数个数K（不超过N的正整数），随后是K个分数，中间以空格分隔。
输出格式：
在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。
输入样例：

1
2
3

10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例：

3 2 0

Solution

def solution(grades, targets):
    result = {target:0 for target in targets}
    for grade in grades:
        if grade in result:
            result[grade] += 1
    print(' '.join(map(str, [result[target] for target in targets])))

input()
grades = list(map(int, input().split()))
targets = list(map(int, input().split()))
solution(grades, targets[1:])

1041 考试座位号(15)

每个PAT考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。
输入格式：
输入第一行给出一个正整数N（<=1000），随后N行，每行给出一个考生的信息：“准考证号试机座位号考试座位号”。其中准考证号由14位数字组成，座位从1到N编号。输入保证每个人的准考证号都不同，并且任何时候都不会把两个人分配到同一个座位上。
考生信息之后，给出一个正整数M（<=N），随后一行中给出M个待查询的试机座位号码，以空格分隔。
输出格式：
对应每个需要查询的试机座位号码，在一行中输出对应考生的准考证号和考试座位号码，中间用1个空格分隔。
输入样例：

4
10120150912233 2 4
10120150912119 4 1
10120150912126 1 3
10120150912002 3 2
2
3 4

输出样例：

1 2	10120150912002 2 10120150912119 1

Solution

def solution(datas, targets):
    for target in targets:
        if target in datas:
            print(datas[target])

n = int(input())
datas = {}
for i in range(n):
    data = input().split()
    datas[data[1]] = data[0] + ' ' + data[2]
input()
targets = input().split()
solution(datas, targets)

1042 字符统计(20)

请编写程序，找出一段给定文字中出现最频繁的那个英文字母。
输入格式：
输入在一行中给出一个长度不超过1000的字符串。字符串由ASCII码表中任意可见字符及空格组成，至少包含1个英文字母，以回车结束（回车不算在内）。
输出格式：
在一行中输出出现频率最高的那个英文字母及其出现次数，其间以空格分隔。如果有并列，则输出按字母序最小的那个字母。统计时不区分大小写，输出小写字母。
输入样例：

1	This is a simple TEST. There ARE numbers and other symbols 1&2&3...........

输出样例：

e 7

Solution

def solution(chars):
    statistical = {}
    for char in chars:
        if char.isalpha():
            if char in statistical:
                statistical[char] += 1
            else:
                statistical[char] = 1
    # 传到key的值为元组，如:('e', 7)
    key = max(sorted(statistical.items()), key=lambda x:x[1])
    print(key[0], key[1])

chars = input().lower()
solution(chars)

1046 划拳(15)

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就赢了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。
下面给出甲、乙两人的划拳记录，请你统计他们最后分别喝了多少杯酒。
输入格式：
输入第一行先给出一个正整数N（<=100），随后N行，每行给出一轮划拳的记录，格式为：
甲喊甲划乙喊乙划
其中“喊”是喊出的数字，“划”是划出的数字，均为不超过100的正整数（两只手一起划）。
输出格式：
在一行中先后输出甲、乙两人喝酒的杯数，其间以一个空格分隔。
输入样例：

输出样例：

1 2

Solution

def solution(records):
  first, second = 0, 0
  for record in records:
    # 甲喊、乙喊、甲划、乙划
    c1, c2, g1, g2 = record[0], record[2], record[1], record[3]
    if g1 == g2:
      continue
    elif c1 + c2 == g1:
      second += 1
    elif c1 + c2 == g2:
      first += 1
  print(first, second)

n = int(input())
records = []
for i in range(n):
    records.append(list(map(int, input().split(' '))))
solution(records)

1047 编程团体赛(20)

编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。
现给定所有队员的比赛成绩，请你编写程序找出冠军队。
输入格式：
输入第一行给出一个正整数N（<=10000），即所有参赛队员总数。随后N行，每行给出一位队员的成绩，格式为：“队伍编号-队员编号成绩”，其中“队伍编号”为1到1000的正整数，“队员编号”为1到10的正整数，“成绩”为0到100的整数。
输出格式：
在一行中输出冠军队的编号和总成绩，其间以一个空格分隔。注意：题目保证冠军队是唯一的。
输入样例：

输出样例：

11 176

Solution

def solution(scores):
    statistical_scores = {}
    for score in scores:
        if score[0] in statistical_scores:
            statistical_scores[score[0]] += int(score[2])
        else:
            statistical_scores[score[0]] = int(score[2])
    team_score = max(statistical_scores.items(), key=lambda x:x[1])
    print(team_score[0], team_score[1])

n = int(input())
scores = []
for i in range(n):
    scores.append(input().replace('-', ' ').split())
solution(scores)

1053 住房空置率（20）

在不打扰居民的前提下，统计住房空置率的一种方法是根据每户用电量的连续变化规律进行判断。判断方法如下：

在观察期内，若存在超过一半的日子用电量低于某给定的阈值 e，则该住房为“可能空置”；

若观察期超过某给定阈值 D 天，且满足上一个条件，则该住房为“空置”。
现给定某居民区的住户用电量数据，请你统计“可能空置”的比率和“空置”比率，即以上两种状态的住房占居民区住房总套数的百分比。
输入格式：
输入第一行给出正整数 N（≤1000），为居民区住房总套数；正实数 e，即低电量阈值；正整数 D，即观察期阈值。随后 N 行，每行按以下格式给出一套住房的用电量数据：
K E1 E2 … EK
其中 K 为观察的天数，Ei 为第 i 天的用电量。
输出格式：
在一行中输出“可能空置”的比率和“空置”比率的百分比值，其间以一个空格分隔，保留小数点后 1 位。
输入样例：

5 0.5 10
6 0.3 0.4 0.5 0.2 0.8 0.6
10 0.0 0.1 0.2 0.3 0.0 0.8 0.6 0.7 0.0 0.5
5 0.4 0.3 0.5 0.1 0.7
11 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
11 2 2 2 1 1 0.1 1 0.1 0.1 0.1 0.1

输出样例：

1	40.0% 20.0%

（样例解释：第2、3户为“可能空置”，第4户为“空置”，其他户不是空置。）
Solution

def solution(n, e, d, dates, consumptions):
    count_maybe, count_must = 0, 0
    for i in range(n):
        consumption = consumptions[i]
        if len(list(filter(lambda x: x < e, consumption))) > len(consumption) / 2:
            count_maybe += 1
            if dates[i] > d:
                count_must += 1
                count_maybe -= 1
    print('{}% {}%'.format(round(count_maybe / n * 100, 1), round(count_must / n * 100, 1)))

n, e, d = input().split()
n, e, d = int(n), float(e), int(d)
dates, consumptions = [], []
for i in range(n):
    data = input().split()
    dates.append(int(data[0]))
    consumptions.append(list(map(float, data[1:])))
solution(n, e, d, dates, consumptions)

本文标题：PAT解题记录
本文作者：Thomas Woo
发布时间：2018-08-03 21:50
最后更新：2020-06-20 15:40
本文链接：http://smileorigin.site/arithmetic/pat/history/
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明出处！

PAT解题记录

1001 害死人不偿命的(3n+1)猜想 (15)

1002 写出这个数 (20)

1004 成绩排名 (20)

1006 换个格式输出整数 (15)

1009 说反话 (20)

1010 一元多项式求导（25）

1011 A+B和C (15)

1012 数字分类 (20)

1017 A除以B（20）

1021 个位数统计 (15)

1023 组个最小数 (20)

1031 查验身份证(15)

1037 在霍格沃茨找零钱（20）

1038 统计同成绩学生(20)

1041 考试座位号(15)

1042 字符统计(20)

1046 划拳(15)

1047 编程团体赛(20)

1053 住房空置率（20）

喜欢这篇文章？打赏一下作者吧

评论

目录

Your browser is out-of-date!