Skip to content

Latest commit

 

History

History
215 lines (147 loc) · 6.89 KB

pat.2.2.md

File metadata and controls

215 lines (147 loc) · 6.89 KB
Raw

霍格沃茨的 A + B 1058 A+B in Hogwarts (20 point(s))

如果你是哈利波特的粉丝，你就会知道魔术世界有其自己的货币体系。

正如海格对哈利解释的那样：“$17$ 个银镰刀（Sickle）可以换 $1$ 个帆船（Galleon），$29$ 个克努特（Knut）可以换 $1$ 个银镰刀。”

你的工作是编写一个计算 $A+B$ 的程序，其中 $A$ 和 $B$ 以 Galleon.Sickle.Knut 的标准形式给出（Galleon 是一个范围在 $[0,10^7]$ 的整数，Sickle 是一个范围在 $[0,17)$ 的整数，Knut 是一个范围在 $[0,29)$ 的整数）。

输入格式

共一行，包含 $A$ 和 $B$，格式如题目所述。

输出格式

按照题目所述标准格式，输出 $A+B$ 的结果。

输入样例：

3.2.1 10.16.27

输出样例：

14.1.28

1058 A+B in Hogwarts (20 point(s))

If you are a fan of Harry Potter, you would know the world of magic has its own currency system -- as Hagrid explained it to Harry, "Seventeen silver Sickles to a Galleon and twenty-nine Knuts to a Sickle, it's easy enough." Your job is to write a program to compute A+B where A and B are given in the standard form of Galleon.Sickle.Knut (Galleon is an integer in $[0,10^7]$, Sickle is an integer in $[0, 17)$, and Knut is an integer in $[0, 29)$).

Input Specification:

Each input file contains one test case which occupies a line with A and B in the standard form, separated by one space.

Output Specification:

For each test case you should output the sum of A and B in one line, with the same format as the input.

#include <iostream>

using namespace std;

int main()
{
    int a, b, c, d, e, f;
    scanf("%d.%d.%d %d.%d.%d", &a, &b, &c, &d, &e, &f);
    a += d, b += e, c += f;

    b += c / 29, c %= 29;  // 先进低位
    a += b / 17, b %= 17;

    printf("%d.%d.%d\n", a, b, c);

    return 0;
}

延迟的回文数 1136 A Delayed Palindrome (20 point(s))

给定一个 $k+1$ 位的正整数 $N$，写成 $a_k \cdots a_1a_0$ 的形式，其中对所有 $i$ 有 $0 \le a_i &lt; 10$ 且 $a_k$ 大于 $0$。

$N$ 被称为一个回文数，当且仅当对所有 $i$ 有 $a_i = a_{k-i}$。

零也被定义为一个回文数。

非回文数也可以通过一系列操作变出回文数。

首先将该数字逆转，再将逆转数与该数相加，如果和还不是一个回文数，就重复这个逆转再相加的操作，直到一个回文数出现。

如果一个非回文数可以变出回文数，就称这个数为延迟的回文数。

给定任意一个正整数，本题要求你找到其变出的那个回文数。

输入格式

输入在一行中给出一个不超过 $1000$ 位的正整数。

输出格式

对给定的整数，一行一行输出其变出回文数的过程。

每行格式如下：

A + B = C

其中 A 是原始的数字，B 是 A 的逆转数，C 是它们的和。A 从输入的整数开始。

重复操作直到 C 在 $10$ 步以内变成回文数，这时在一行中输出 C is a palindromic number.；

或者如果 $10$ 步都没能得到回文数，最后就在一行中输出 Not found in 10 iterations.。

输入样例1：

97152

输出样例1：

97152 + 25179 = 122331
122331 + 133221 = 255552
255552 is a palindromic number.

输入样例2：

196

输出样例2：

196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.

1136 A Delayed Palindrome (20 point(s))

Consider a positive integer N written in standard notation with k+1 digits $a_i$ as $a_k \cdots a_1a_0$ with $0 \le a_i &lt; 10$ for all i and $a_k&gt;0$. Then N is palindromic if and only if $a_i = a_{k−i}$ for all i. Zero is written 0 and is also palindromic by definition.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. Such number is called a delayed palindrome. (Quoted from https://en.wikipedia.org/wiki/Palindromic_number )

Given any positive integer, you are supposed to find its paired palindromic number.

Input Specification:

Each input file contains one test case which gives a positive integer no more than 1000 digits.

Output Specification:

For each test case, print line by line the process of finding the palindromic number. The format of each line is the following:

A + B = C

where A is the original number, B is the reversed A, and C is their sum. A starts being the input number, and this process ends until C becomes a palindromic number -- in this case we print in the last line C is a palindromic number.; or if a palindromic number cannot be found in 10 iterations, print Not found in 10 iterations. instead.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

bool check(vector<int> A)
{
    for (int i = 0, j = A.size() - 1; i < j; i ++, j -- )
        if (A[i] != A[j])
            return false;
    return true;
}

void print(vector<int> A)
{
    for (int i = A.size() - 1; i >= 0; i -- ) cout << A[i];
}

vector<int> add(vector<int> A, vector<int> B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    return C;
}

int main()
{
    string a;
    cin >> a;

    vector<int> A;
    for (int i = 0; i < a.size(); i ++ ) A.push_back(a[a.size() - 1 - i] - '0');  // 从低位开始存

    for (int i = 0; i < 10; i ++ )
    {
        if (check(A)) break;
        vector<int> B(A.rbegin(), A.rend());  // 翻转 vector 可以用 `vector<int> B(A.rbegin(), A.rend());`

        print(A), cout << " + ", print(B), cout << " = ";
        A = add(A, B);

        print(A), cout << endl;
    }

    if (check(A)) print(A), cout << " is a palindromic number." << endl;
    else puts("Not found in 10 iterations.");

    return 0;
}