Lời Giải HSG Tin Tỉnh Quảng Ninh (B) - 2020

Author Hung Nguyen Tuong

Bài 1. Tổng cặp số

Cho số nguyên dương $N$ và $2$ dãy số nguyên dương $A_1,A_2,...,A_N, \ B_1,B_2,...,B_N$.

Yêu cầu

Viết chương trình tính tổng các cặp số $A_i$ và $B_i \ (1 \le i \le N)$. Ghi ra các tổng có giá trị là chẵn.

Dữ liệu

Vào từ tệp TONGCAPSO.INP gồm:

• Dòng đầu tiên: Chứa số nguyên dương $N \ (1 \le N \le 10^3)$.
• $N$ dòng tiếp theo: Dòng thứ $i$ chứa 2 số nguyên dương $A_i$ và $B_i \ (1 \le A_i, B_i \le 10^{64})$.

Kết quả

Ghi ra tệp TONGCAPSO.OUT các dòng chứa tổng có giá trị là chẵn theo yêu cầu bài toán. Các tổng ghi ra theo thứ tự từ $1$ đến $N$.

Ví dụ

Ràng buộc

• $60\%$ số test ứng với $60\%$ số điểm của bài có $A_i, B_i \le 10^3$.
• $20\%$ số test ứng với $20\%$ số điểm của bài có $A_i, B_i \le 10^{18}$.
• $20\%$ số test ứng với $20\%$ số điểm của bài có $A_i, B_i \le 10^{64}$.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int ctoi(char c)
{
    return (int)c - 48;
}
bool isEven(string A, string B)
{
    return (ctoi(A.back()) + ctoi(B.back())) % 2 == 0;
}
string bigNum(string A, string B)
{
    if (A.size() < B.size())
        swap(A, B);

    string ans = "";
    int r = 0, d = A.size() - B.size();

    for (int i = A.size() - 1; i >= 0; i--)
    {
        int cur = (i - d >= 0 ? ctoi(B[i - d]) : 0) + ctoi(A[i]) + r;
        r = 0;

        if (cur > 9)
        {
            r = 1;
            cur %= 10;
        }
        ans += to_string(cur);
    }

    if (r == 1)
        ans += "1";

    reverse(ans.begin(), ans.end());
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string A, B;
        cin >> A >> B;
        if (!isEven(A, B))
            continue;
        cout << bigNum(A, B) << nl;
    }
    return 0;
}

Bài 2. Thống kê xâu

Cho xâu $S$ gồm các kí tự được lấy từ $(a,b,...,z, \ A,B,...,Z, \ 0,1,2,...,9)$, xâu $S$ không chứa dấu cách.

Yêu cầu

Hãy viết chương trình đếm số lượng các loại kí tự khác nhau của xâu $S$, tính tần số xuất hiện của từng loại kí tự.

Dữ liệu

Vào từ tệp THONGKEXAU.INP một dòng duy nhất chứa xâu $S$.

Kết quả

Ghi ra tệp THONGKEXAU.OUT gồm các dòng:

• Dòng đầu tiên gồm 1 số nguyên là số loại kí tự khác nhau có trong xâu $S$.
• Các dòng tiếp theo:
  • Mỗi dòng ghi số lần xuất hiện của một kí tự trong xâu $S$, dấu cách và kí tự đó. Nếu số lần xuất hiện của một kí tự là 1 thì chỉ ghi ra kí tự.
  • Các kí tự ghi ra theo thứ tự chữ số, chữ cái in thường, chữ cái in hoa.
  • Các kí tự chữ số ghi ra theo thứ tự $0,1,2,...,9$; các kí tự chữ cái in thường ghi ra theo thứ tự $a,b,...,z$; các kí tự chữ cái in hoa ghi ra theo thứ tự $A,B,...,Z$.

Ví dụ

Ràng buộc

• Có $40\%$ số test ứng với $40\%$ số điểm của bài với xâu $S$ chỉ xuất hiện các loại kí tự thuộc nhóm $a,b,...,z$ hoặc $A,B,...,Z$ hoặc $0,1,2,...,9$; và độ dài xâu $S$ tối đa là $255$ kí tự.
• Có $30\%$ số test ứng với $30\%$ số điểm của bài với độ dài xâu $S$ tối đa là $1000$ kí tự.
• Có $30\%$ số test ứng với $30\%$ số điểm của bài với độ dài xâu $S$ tối đa là $500000$ kí tự.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int chr[256];
void output(char low, char high)
{
    for (char i = low; i <= high; i++)
    {
        if (chr[(int)i] == 0)
            continue;
        if (chr[(int)i] != 1)
            cout << chr[(int)i] << " ";
        cout << i << nl;
    }
}
int main()
{
    string s;
    cin >> s;
    int cnt = 0;
    memset(chr, 0, sizeof(chr));
    for (auto i : s)
    {
        if (chr[(int)i] == 0)
            cnt++;
        chr[(int)i]++;
    }
    cout << cnt << nl;
    output('0', '9');
    output('a', 'z');
    output('A', 'Z');
    return 0;
}

Bài 3. Ước số

Cho số nguyên $q$ và hai dãy số nguyên dương $a_1,a_2,...,a_q,b_1,b_2,...,b_q$.

Yêu cầu

Với mỗi $i \ (1 \le i \le q)$ bạn hãy đếm số ước nguyên dương của $n_i$ với $n_i = a_i*b_i$.

Dữ liệu

Vào từ tệp UOCSO.INP gồm các dòng:

• Dòng đầu tiên chứa 1 số nguyên dương $q$.
• $q$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $a_i,b_i$.

Kết quả

Ghi ra tệp UOCSO.OUT gồm $q$ dòng, dòng thứ $i \ (1 \le i \le q)$ ghi một số nguyên duy nhất là số lượng ước nguyên dương của $n_i$.

Ví dụ

Ràng buộc

• Có $60\%$ số test ứng với $60\%$ số điểm của bài có $a_i,b_i \le 10^2, \ q=1$.
• Có $20\%$ số test ứng với $20\%$ số điểm của bài có $a_i,b_i \le 10^6, \ q \le 10$.
• Có $20\%$ số test ứng với $20\%$ số điểm của bài có $a_i,b_i \le 10^6, \ q \le 100$.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef map<int, int> mpii;
#define nl '\n'

map<ll, int> numOfDivisors;

mpii fact(ll n)
{
    mpii ans;
    while (n % 2 == 0)
    {
        ans[2]++;
        n /= 2;
    }
    for (int i = 3; i <= sqrt(n); i += 2)
    {
        while (n % i == 0)
        {
            n /= i;
            ans[i]++;
        }
    }
    if (n > 1)
        ans[n]++;
    return ans;
}

int solve()
{
    ll a, b, prod;
    cin >> a >> b;
    prod = a * b;

    if (numOfDivisors.find(prod) != numOfDivisors.end())
    {
        return numOfDivisors[prod];
    }

    if (prod == 1)
        return 1;

    mpii fab, fa = fact(a), fb = fact(b);
    for (auto i : fa)
        fab[i.first] += i.second;
    for (auto i : fb)
        fab[i.first] += i.second;

    int ans = 1;
    for (auto i : fab)
        ans *= (i.second + 1);

    numOfDivisors[prod] = ans;
    return ans;
}

int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        cout << solve() << nl;
    }
    return 0;
}