Thwrani's questions

一些银行希望实施支持以下操作的客户账户管理系统： -
为客户账户充值；
- 从账户中取款；
- 要求账户上的资金余额；
- 客户账户之间的汇款；
- 计算所有客户的利息。
有必要实施这样的系统。银行客户由其名称（不包含空格的唯一字符串）标识。最初，该银行没有一个客户。一旦客户进行存款、取款或转账，他就会获得一个余额为零的账户。所有进一步的操作都只用这个帐户进行。帐户上的金额可以是正数也可以是负数，但它始终是整数。

首先，输入要执行的操作数 n (n <= 50000)。接下来的 n 行包含操作本身：

DEPOSIT name sum — 将金额总和记入客户名称的账户。如果客户没有帐户，则创建一个帐户。
WITHDRAW name sum - 从客户名称的账户中提取金额。如果客户没有帐户，则创建一个帐户。
余额名称 - 找出客户帐户名称上的余额。
TRANSFER name1 name2 sum — 将金额 sum 从客户 name1 的账户转移到客户 name2 的账户。如果客户没有帐户，则会为他创建一个帐户。
INCOME p — 将账户金额的 p% 计入所有已开立账户的客户。只有账户余额为正的客户才会产生利息，如果客户的余额为负，那么他的账户不会改变。计息后，账户上的金额保持不变，即只计提整数个货币单位。应计利息的小数部分被丢弃。

对于每个 BALANCE 请求，必须显示该客户帐户的余额。如果具有请求名称的客户没有银行帐户，则打印 ERROR。
示例：
输入：
7
存款 Ivanov 100
收入 5
余额 Ivanov
转账 Ivanov Petrov 50
取款 Petrov 100
余额 Petrov
余额 Sidorov
输出：
105
-50
错误

我用 C++ 编写了代码：

#include <iostream>
#include <map>
#include <string>
using namespace std;

void deposit(map<string, long long> &bank, string &name, long long &sum)
{
    if (bank.find(name) == bank.end())
        bank[name] = 0;
    bank[name] += sum;
}
void withdraw(map<string, long long> &bank, string &name, long long &sum)
{
    if (bank.find(name) == bank.end())
        bank[name] = 0;
    bank[name] -= sum;
}
string balance(map<string, long long> &bank, string &name)
{
    if (bank.find(name) == bank.end())
        return "ERROR";
    return to_string(bank[name]);
}
void income(map<string, long long> &bank, float percent)
{
    for (auto it = bank.begin(); it != bank.end(); ++it)
    {
        if (it->second > 0)
        {
            bank[it->first] = it->second * (100 + percent) / 100;
        }
    }
}
int main()
{
    map<string, long long> bank;
    long long n, val; cin >> n;
    string command, name, name2;
    for (long long i = 0; i < n; i++)
    {
        cin >> command;
        if (command == "DEPOSIT")
        {
            cin >> name >> val;
            deposit(bank, name, val);
        }
        else if (command == "WITHDRAW")
        {
            cin >> name >> val;
            withdraw(bank, name, val);
        }
        else if (command == "BALANCE")
        {
            cin >> name;
            cout << balance(bank, name) << endl;
        }
        else if (command == "TRANSFER")
        {
            cin >> name >> name2 >> val;
            withdraw(bank, name, val);
            deposit(bank, name2, val);
        }
        else if (command == "INCOME")
        {
            float value;
            cin >> value;
            income(bank, value);
        }
    }
}

在某些测试中，它显示错误的答案。我无法弄清楚错误在哪里。请告诉我它可以在哪里以及如何修复它？（我不知道测试数据...）

有一个任务：

超数是一个数字，它是 [2…B] 范围内的两个素数之和。需要找到给定范围 [A…B] 中的所有超数。(2 <= A <= B <= 40000)
示例：输入：3 10；输出：4 5 6 7 8 9 10

我写了python代码：

a, b = map(int, input().split())
 
prime = [x for x in range(b + 1)]
prime[1] = 0
prime_list = []
 
i = 2
while i <= b:
    if prime[i] != 0:
        prime_list.append(prime[i])
        for j in range(i, b - 1, i):
            prime[j] = 0
    i += 1
 
ans = []
for i in range(len(prime_list)):
    for x in range(0, len(prime_list) - 1):
        g = prime_list[i] + prime_list[x]
        ans.append(g) if g <= b and g >= a else None
 
ans = sorted(list(set(ans)))
for x in ans:
    print(x)

在 C++ 中

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
    int a; int b;
    cin >> a >> b;
    vector<int> prime (0);
    vector<int> prime_list (0);
    for (int i = 0; i <= b; i++)
        prime.push_back(i);
    prime[0] = 1;
    int i = 2;
    while (i <= b)
    {
        if (prime[i] != 0)
        {
            prime_list.push_back(prime[i]);
            for (int j = i; j < b - 1; j *= 2)
                prime[j] = 0;
        }
        i += 1;
    }
    set<int> ans;
    for (int i = 0; i < prime_list.size(); i++)
    {
        for (int x = 0; x < prime_list.size() - 1; x++)
        {
            int g = prime_list[i] + prime_list[x];
            if (g <= b && g >= a)
                ans.insert(g);
        }
    }
    for (int x: ans)
        cout << x << endl;
}

Python 通过了所有测试，但 C++“在执行过程中出错”。
你能告诉我C++代码有什么问题吗？（我不知道的测试数据）

给定任务：

为了检查她的学生如何数数，Ma​​ria Ivanovna 每年都会在家里给他们布置相同的任务 - 对于给定的自然 A，找到最小自然 N 使得 N 的 N 次方（N 乘以自身 N 次）是能被 A 整除。有必要写一个程序来解决这个问题

1 ≤ A ≤ 10^9
我写了这段代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>
using namespace std;
vector<int> decomp (int n)
{
    vector<int> ans (0);
    int d = 2;
    while (d * d <= n)
    {
        if (n % d == 0)
        {
            ans.push_back(d);
            n /= d;
        }
        else
            d += 1;
    }
    if (n > 1)
        ans.push_back(n);
    return ans;
}
int main()
{
    int x; cin >> x;
    if (x == 1)
        cout << 1;
    else
    {
        vector<int> tmp = decomp(x);
        unordered_set<int> s;
        for (int el: tmp)
            s.insert(el);
        vector<int> a (0);
        for (int el: s)
            a.push_back(el);
        int y = 1;
        for (int i = 0; i < a.size(); i++)
            y *= a[i];
        if (y >= 29)
            cout << y;
        else
        {
            int k = 1; int n = k * y;
            while ((int)pow(n, n) % x != 0)
            {
                n = k * y;
                k += 1;
            }
            cout << n;
        }
    }
}

但是它运行得太慢了。请帮助我，我该如何优化它？

索菲亚发现一个数字很有趣，如果它的数字是非递减顺序的。例如，数字 123、1111 或 888999 很有趣。

索菲亚对存在多少有趣的正数感兴趣，这些正数存在于从 L 到 R 的范围内。这个数字对于大的 L 和 R 来说可能非常大，所以 Sofia 想要找到这个数字除以 10^9+7 后的余数。

需要编写一个程序，在给定 L 和 R 的情况下，确定 L 到 R（包括 L 到 R）范围内的有趣数字的数量，并显示该数字除以 10^9+7 后的余数。

限制：1 <= L <= R <= 10^100

示例：输入：1\n100 输出：54

我用python写了这段代码：

def f(n):
    res, min_num = 0, 0
    for i, j in enumerate(n):
        j = int(j)
        if j < min_num: 
            return res
        elif j > min_num:
            res += sum(a[len(n) - i][9 - x] for x in range(min_num, j))
            min_num = j
    return res + 1
L = input()
R = input()
p = 10 ** 9 + 7 
s = len(R)
a = [[0] * 10 for _ in range(s + 1)]
a[0][0] = 1
for k in range(1, s + 1):
    for i in range(10):
        a[k][i] = sum(a[k - 1][j] for j in range(i + 1))
print((f(R) - f(str(int(L) - 1))) % p)

这是相同的算法，仅在 C++ 中：

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <numeric>
using namespace std;
const long long p = pow(10, 9) + 7;
string decrease(string str)
{
    //Уменьшает число в строке на 1
    int l = str.length();
    if (str[l - 1] == '0')
    {
        int i = l - 1;
        while (str[i] == '0' && i > 0)
        {
            str = str.substr(0, i) + "9" + str.substr(i + 1, l);
            i--;
        }
        str = str.substr(0, i) + to_string(str[i] - '0' - 1) + str.substr(i + 1, l);
        return str;
    }
    else
        return str.substr(0, l - 1) + to_string(str[l - 1] - '0' - 1);
}
long long f(string n, vector<vector<long long>> a)
{
    long long res = 0; long long min_num = 0;
    for (int i = 0; i < n.length(); i++)
    {
        int j = n[i] - '0';
        if (j < min_num)
            return res;
        else if (j > min_num)
        {
            vector<long long> tmp (0);
            for (int x = min_num; x < j; x++)
                tmp.push_back(a[n.length() - i][9 - x]);
            res = (res + accumulate(tmp.begin(), tmp.end(), 0)) % p;
            min_num = j;
        }
    }
    return res + 1;
}
int main()
{
    string l; string r;
    cin >> l;
    cin >> r;
    long long s = r.length();
    vector<long long> tmp (10, 0);
    vector<vector<long long>> a (s + 1, tmp);
    a[0][0] = 1;
    for (int k = 1; k <= s; k++)
    {
        for (int i = 0; i < 10; i++)
        {
            vector<long long> tmp (0);
            for (int j = 0; j <= i; j++)
                tmp.push_back(a[k - 1][j]);
            a[k][i] = accumulate(tmp.begin(), tmp.end(), 0) % p;
        }
    }
    cout << (f(r, a) - f(decrease(l), a)) % p;
}

Python 代码通过了所有测试，但 C++ 代码将在 0 秒后的第一次测试中崩溃（给出错误答案）。请帮忙，C++代码有什么问题？（我不知道测试数据） C++ 代码已更改。将 to_str(stoll(l) - 1) 更改为执行相同操作的函数，但将 l 保留为字符串。它仍然无法正常工作......

如果一个数字的数字从最高有效数字开始形成一个非递减序列，我们就称它为平滑数字。按升序对所有这些数字进行排序，并为每个数字分配一个数字。需要输出第N个平滑数N。

1 <= N <= 2147483647

例子：

Ввод: 3 Вывод: 3
Ввод: 11 Вывод: 12

我用 Python 写了这段代码：

n = int(input())
result = ""
#В dp[i][j] записано кол-во гладких чисел длины i, начинающихся на цифру j
dp = [[0] * 10 for _ in range(n + 1)] #я немного не понял, откуда надо брать длину dp
for j in range(10):
    dp[1][j] = 1
for i in range(2, n):
    for j in range(10):
        dp[i][j] = sum(dp[i - 1][k] for k in range(10) if k >= j)
#Находим длину n-го гладкого числа
n_l = 1
for i in range(1, n):
    if dp[i + 1][0] >= n and dp[i][0] < n:
        n_l = i
        break
n -= dp[n_l][0]
#Находим первую цифру числа
j = 1
while n >= dp[n_l][j]:
    n -= dp[n_l][j]
    j += 1
result += str(j)
prev = j
#Находим оставшиеся цифры числа
if n_l > 1:
    while n > 0:
        for j in range(prev + 1, 10):
            if n <= dp[i - 1][j]:
                n -= dp[i - 1][j]
                result += str(j)
                prev = j
                break
            n -= dp[n_l - 1][j]
print(result)

此代码仅适用于 N 的小值。我应该在其中修复什么以便它适用于 N 的大值（N <= 2147483647）