杭电HDU-ACM – 1001 – Sum Problem

Problem Description

Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).

In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + … + n.

Input

The input will consist of a series of integers n, one integer per line.

Output

For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.

Sample Input

1
100

Sample Output

1

5050

题目大意:

给定一个数,计算1+2+…+n的值。

代码:

#include <iostream>
using namespace std;

__int64 Sum(int num){
    __int64 sum{};
    !(num % 2) ? sum = num / 2 * (1 + num) : sum = (1 + num) / 2 * num;
    return sum;
}

int main() {
    for(int num{}; cin >> num && !cin.eof(); cout << Sum(num) << endl << endl);
    return 0;
}

杭电HDU-ACM – 1000 – A + B Problem

Problem Description

Calculate A + B.

Input

Each line will contain two integers A and B. Process to end of file.

Output

For each case, output A + B in one line.

Sample Input

1 1

Sample Output

2

题目大意:

给定两个数,计算其和。

坑点:

是多测试例,需要使用循环,并且循环需要判断是否为EOF,否则会超时。

代码:

#include <iostream>
using namespace std;

int main() {
    for(int a{}, b{}; cin >> a >> b && !cin.eof(); cout << a + b << endl);
}

PAT乙级真题 – 1037 在霍格沃茨找零钱 (20point(s))

如果你是哈利·波特迷,你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的:“十七个银西可(Sickle)兑一个加隆(Galleon),二十九个纳特(Knut)兑一个西可,很容易。”现在,给定哈利应付的价钱 P 和他实付的钱 A,你的任务是写一个程序来计算他应该被找的零钱。

输入格式:

输入在 1 行中分别给出 P 和 A,格式为 Galleon.Sickle.Knut,其间用 1 个空格分隔。这里 Galleon 是 [0, 10​7​​] 区间内的整数,Sickle 是 [0, 17) 区间内的整数,Knut 是 [0, 29) 区间内的整数。

输出格式:

在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱,那么输出的应该是负数。

输入样例 1:

10.16.27 14.1.28

      
    

输出样例 1:

3.2.1

      
    

输入样例 2:

14.1.28 10.16.27

      
    

输出样例 2:

-3.2.1

思路:

先全部转knut计算,最终计算结果再转回来

代码(Python):

need, paid = map(str, input().split())


def transform(num):
    galleon, sickle, knut = map(int, num.split('.'))
    sickle += galleon * 17
    knut += sickle * 29
    return knut


need = transform(need)
paid = transform(paid)
paid -= need


def transform_back(num):
    flag = False
    if num < 0:
        flag = True
        num = abs(num)
    galleon = num // 29 // 17
    num -= galleon * 17 * 29
    sickle = num // 29
    knut = num - sickle * 29
    s = '{}.{}.{}'.format(galleon, sickle, knut)
    if flag:
        s = '-{}'.format(s)
    return s


print(transform_back(paid))

PAT乙级真题 – 1036 跟奥巴马一起编程 (15point(s))

美国总统奥巴马不仅呼吁所有人都学习编程,甚至以身作则编写代码,成为美国历史上首位编写计算机代码的总统。2014 年底,为庆祝“计算机科学教育周”正式启动,奥巴马编写了很简单的计算机代码:在屏幕上画一个正方形。现在你也跟他一起画吧!

输入格式:

输入在一行中给出正方形边长 N(3≤N≤20)和组成正方形边的某种字符 C,间隔一个空格。

输出格式:

输出由给定字符 C 画出的正方形。但是注意到行间距比列间距大,所以为了让结果看上去更像正方形,我们输出的行数实际上是列数的 50%(四舍五入取整)。

输入样例:

10 a

      
    

输出样例:

aaaaaaaaaa
a        a
a        a
a        a
aaaaaaaaaa

代码:

#include <iostream>
using namespace std;

int main() {
    char out{};
    int col{}, row{}; cin >> col >> out;
    row = int(double(col) / 2 + 0.5);
    for(int i{1}; i <= row; i++){
        for(int j{1}; j <= col; j++)
            if(i == 1 || i == row || j == 1 || j == col) cout << out;
            else cout << " ";
        cout << endl;
    }
    return 0;
}

PAT乙级真题 – 1035 插入与归并 (25point(s))

根据维基百科的定义:

插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作:首先将原始序列看成 N 个只包含 1 个元素的有序子序列,然后每次迭代归并两个相邻的有序子序列,直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列,请你判断该算法究竟是哪种排序算法?

输入格式:

输入在第一行给出正整数 N (≤100);随后一行给出原始序列的 N 个整数;最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式:

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序;然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔,且行首尾不得有多余空格。

输入样例 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

      
    

输出样例 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

      
    

输入样例 2:

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

      
    

输出样例 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

代码:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> va;
vector<int> vb;
int main() {
    int n; cin >> n;
    int temp, i;
    for(i = 0; i < n; cin >> temp, va.push_back(temp), i++);
    for(i = 0; i < n; cin >> temp, vb.push_back(temp), i++);
    for(i = 0; i < n - 1 && vb[i] <= vb[i + 1]; temp = i + 2, i++);
    bool flag = true;
    for(i = temp + 1; i < n; i++){
        flag = va[i] == vb[i];
        if(!flag) break;
    }
    if(flag){
        cout << "Insertion Sort" << endl;
        sort(vb.begin(), vb.begin() + min(temp + 1, n));
    }else{
        cout << "Merge Sort" << endl;
        int m = 2;
        int sorted;
        s:
        for(i = 0; i < n; i += m){
            sorted = is_sorted(vb.begin() + i, vb.begin() + min(i + m, n));
            if(sorted == 0) break;
        }
        if(sorted){
            m *= 2; goto s;
        }
        for(i = 0; i < n; i += m)
            sort(vb.begin() + i, vb.begin() + min((i + m), n));
    }
    for(auto it = vb.begin(); it != vb.end(); it++)
        printf("%s%d",it == vb.begin() ? "" : " ", *it);
    return 0;
}

PAT乙级真题 – 1034 有理数四则运算 (20point(s))

本题要求编写程序,计算 2 个有理数的和、差、积、商。

输入格式:

输入在一行中按照 a1/b1 a2/b2 的格式给出两个分数形式的有理数,其中分子和分母全是整型范围内的整数,负号只可能出现在分子前,分母不为 0。

输出格式:

分别在 4 行中按照 有理数1 运算符 有理数2 = 结果 的格式顺序输出 2 个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式 k a/b,其中 k 是整数部分,a/b 是最简分数部分;若为负数,则须加括号;若除法分母为 0,则输出 Inf。题目保证正确的输出中没有超过整型范围的整数。

输入样例 1:

2/3 -4/2

      
    

输出样例 1:

2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

      
    

输入样例 2:

5/3 0/6

      
    

输出样例 2:

1 2/3 + 0 = 1 2/3
1 2/3 - 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

代码(Python):

import fractions


def out_format(num):
    num = str(num)
    s = False
    if '-' in num:
        s = True
        num = num[1:]
    if '/' in num:
        temp = [int(i) for i in num.split('/')]
        if temp[0] > temp[1]:
            x1 = temp[0] // temp[1]
            x2 = temp[0] % temp[1]
            num = '{} {}/{}'.format(x1, x2, temp[1])
    if s:
        num = '(-{})'.format(num)
    return num


def calculate(flag, n):
    try:
        if flag == '+':
            result = fractions.Fraction(n[0] * n[3] + n[2] * n[1], n[1] * n[3])
            return result
        if flag == '-':
            result = fractions.Fraction(n[0] * n[3] - n[2] * n[1], n[1] * n[3])
            return result
        if flag == '*':
            result = fractions.Fraction(n[0] * n[2], n[1] * n[3])
            return result
        if flag == '/':
            result = fractions.Fraction(n[0] * n[3], n[1] * n[2])
            return result
    except:
        result = 'Inf'
        return result


n = input().split()
n = [int(i) for i in (n[0].split('/') + n[1].split('/'))]
n1 = fractions.Fraction(n[0], n[1])
n2 = fractions.Fraction(n[2], n[3])
n1 = out_format(n1)
n2 = out_format(n2)

flag = ['+', '-', '*', '/']
for i in flag:
    result = calculate(i, n)
    if result != 'Inf':
        result = out_format(result)
    print('{0} {1} {2} = {3}'.format(n1, i, n2, result))

PAT乙级真题 – 1033 旧键盘打字 (20point(s))

旧键盘上坏了几个键,于是在敲一段文字的时候,对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键,打出的结果文字会是怎样?

输入格式:

输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出;每段文字是不超过 10​5​​ 个字符的串。可用的字符包括字母 [azAZ]、数字 09、以及下划线 _(代表空格)、,.-+(代表上档键)。题目保证第 2 行输入的文字串非空。

注意:如果上档键坏掉了,那么大写的英文字母无法被打出。

输出格式:

在一行中输出能够被打出的结果文字。如果没有一个字符能被打出,则输出空行。

输入样例:

7+IE.
7_This_is_a_test.

      
    

输出样例:

_hs_s_a_tst

思路:

利用map存放坏键,在map中寻找’+’,若存在则不输出大写字母。因为坏键是以大写字母输入,所以在map中寻找其他坏键时需要使用toupper。

代码:

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<char, bool> mmap;
int main() {
    string bad{}, input{};
    getline(cin, bad);
    getline(cin, input);
    for (auto i : bad) mmap[i] = true;
    auto shift{mmap.find('+')};
    bool flag{shift != mmap.end()};
    for (auto i : input) {
        if ((flag && isupper(i)) || i == '+') continue;
        auto mit{mmap.find(toupper(i))};
        if (mit == mmap.end()) cout << i;
    }
    return 0;
}

PAT乙级真题 – 1032 挖掘机技术哪家强 (20point(s))

为了用事实说明挖掘机技术到底哪家强,PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入格式:

输入在第 1 行给出不超过 10​5​​ 的正整数 N,即参赛人数。随后 N 行,每行给出一位参赛者的信息和成绩,包括其所代表的学校的编号(从 1 开始连续编号)、及其比赛成绩(百分制),中间以空格分隔。

输出格式:

在一行中给出总得分最高的学校的编号、及其总分,中间以空格分隔。题目保证答案唯一,没有并列。

输入样例:

6
3 65
2 80
1 100
2 70
3 40
3 0

      
    

输出样例:

2 150

思路:

使用map进行数据的存储,在读入过程中比较最大的分数,并存放至变量中,读取所有数据后输出最大值即可。

代码:

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, int> mmap;
int main() {
    int n{}; cin >> n;
    int id{}, score{}, max{}, max_id{};
    while(n--){
        cin >> id >> score;
        mmap[id] += score;
        mmap[id] >= max ? max_id = id, max = mmap[id] : 0;
    }
    cout << max_id << " " << max << endl;
    return 0;
}

PAT乙级真题 – 1031 查验身份证 (15point(s))

一个合法的身份证号码由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:

12010X198901011234
110108196711301866
37070419881216001X

      
    

输入样例2:

2
320124198808240056
110108196711301862

      
    

输出样例2:

All passed

      
    

鸣谢阜阳师范学院范建中老师补充数据

鸣谢浙江工业大学之江学院石洗凡老师纠正数据

思路:

先将题目中的数据存放到map及数组中,使用getline读入一行,这里因为中间不会出现空格,使用cin也可,然后前17个根据权重计算出的数值与最后一个比较,如果不同则代表有问题,存入vector中。最后判断vector是否为空,若为空说明全部通过,否则逐条输出。

代码:

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int, char> mmap{
        {0, '1'},
        {1, '0'},
        {2, 'X'},
        {3, '9'},
        {4, '8'},
        {5, '7'},
        {6, '6'},
        {7, '5'},
        {8, '4'},
        {9, '3'},
        {10, '2'}
};
int weight[17]{7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
vector<string> v;
int main() {
    int n{}; (cin >> n).get();
    string temp{};
    while(n--){
        int sum{};
        getline(cin, temp);
        for(int i{}; i < 17; i++)
            sum += weight[i] * (temp[i] - '0');
        sum %= 11;
        if(mmap[sum] != temp[17]) v.push_back(temp);
    }
    if(v.empty()) cout << "All passed" << endl;
    else for(auto it :v) cout << it << endl;
    return 0;
}

PAT乙级真题 – 1030 完美数列 (25point(s))

给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 Mmp,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

输入格式:

输入第一行给出两个正整数 N 和 p,其中 N(≤10​5​​)是输入的正整数的个数,p(≤10​9​​)是给定的参数。第二行给出 N 个正整数,每个数不超过 10​9​​。

输出格式:

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例:

10 8
2 3 20 4 5 1 6 7 8 9

      
    

输出样例:

8

代码:

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> Vector;
int main() {
    Vector v;
    int N, temp;
    long long p;
    cin >> N >> p;
    while(N--){
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    int position = 0;
    for(int i = 0; i < v.size() ;i++){
        for(int j = i + position; j < v.size(); j++){
            if(v[j] <= v[i] * p){
                if(j - i + 1 > position)
                    position = j - i + 1;
            }else{
                break;
            }
        }
    }
    cout << position << endl;
    return 0;
}