1010 Radix (25 points)

• Topic: radix digits
• Topic: Give the base of two numbers and one of them, ask if the other number can be equal to this number in a certain base.
• Ideas: If tag equals 2, swap, and finally just need to deal with tag 1, this idea is worth learning; The first step is to convert n1 to decimal, and consider if this can be saved. n1 does not exceed ten digits, so the maximum is ten z, or thirty-six digits. Ten Z is less than one, followed by ten zeros, or less than one 3 6 10 36^{10} 3610, 3e15 more, that is, you can save with long long long; The second step is to determine what base n2 is equal to target, noting that n2 may be more than 36, such as n2 is ( 10 ) b = b (10)_b=b (10)b = b, n1 is 3e15 at the maximum, so we can get a 3e15 power at the maximum, so we enumerate more than 36 times, that is, the enumeration range is very large, so we thought if we could use two points to find it. We found that when the enumeration progress gets bigger, n2 gets bigger, which is a monotonous process. So we can find this binary with a dichotomy;
• Bisection requires a left and right boundary, the right boundary is target+1, and the left boundary should be equal to the largest bit of n2 plus 1
• In calc, res may explode long, if it is too large, greater than 1e16 already, we know that the maximum value of n1 is 3e15, at this time there must be no solution, it will return 1e18 directly; Note that the binary r of the parameter in Calc is also long long long
• r If you take the target directly, the 6.61.10 sample returns 6, but the answer is 7.
• Notice how the code actively converts an int to a long long long multiple times
• The result of multiplying two numbers may not be long long, overflow may become negative or positive, so use double
• Syntax: swap function in algorithm header file

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int get(char c)
{
    if (c <= '9') return c - '0';
    return c - 'a' + 10;
}

ll calc(string n, ll r)
{
    ll res = 0;
    for (auto c : n)
    {
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);
    }
    return res;
}

int main()
{
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;
    
    if (tag == 2) swap(n1, n2);
    ll target = calc(n1, radix);
    
    ll l = 0, r = target + 1;
    // ll l = 0, r = max(target, 36ll);
    for (auto c : n2) l = max(l, (ll)get(c) + 1);
    
    while (l < r)
    {
        ll mid = l + r >> 1;
        if (calc(n2, mid) >= target) r = mid;       // == problem!
        else l = mid + 1;
    }
    
    if (calc(n2, r) == target) cout << r;
    else cout << "Impossible";
    
    return 0;
}

1015 Reversible Primes (20 points)

• Topic: First judge if N is a prime number. Then N is converted to D-ary number, and D-ary number is flipped back to decimal number to see if this number is prime.
• Ideas: n n n% d d D is the last digit of n in the d-digit, that is, the digit in the d-digit. After flipping, this should be the first digit. When you turn the result of flipping into decimal, you start with the highest digit. This converts the last three steps into one.
• Syntax: The value of a comma expression is the last value; N N N Max is 1 0 5 10^5 105, then if it is binary there will be more than a dozen, fifteen or sixteen, so use l o n g l o n g long long longlong stores the result after the conversion.

#include <iostream>

using namespace std;

typedef long long LL;

bool is_prime(int n)
{
    if (n == 1) return false;
    
    for (int i = 2; i * i <= n; i ++ )
        if (n % i == 0)
            return false;
    return true;
}

bool check(int n, int d)
{
    if (!is_prime(n)) return false;
    
    LL r = 0;
    while (n)
    {
        r = r * d + n % d;
        n /= d;
    }
    
    return is_prime(r);
}

int main()
{
    int n, d;
    while (cin >> n >> d, n >= 1)
    {
        if (check(n, d)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

1019 General Palindromic Number (20 points)

• Title: Give a number and a decimal number to determine if the result of this number in this decimal number is palindrome number.
• Ideas: Judge palindromes (i just <j); Decimal to other decimal, easier to store with vectors; Decimal to other decimal, note that the case where n is 0 is discussed in particular. When decimal is converted to other binaries, the lowest bit in the other binary is obtained first, because it is first placed in a vector, and when it outputs this number in the other binary, it is output from the highest bit to the lowest bit, so it starts from the last bit in the vectors.
• Syntax: reverse function in algorithm header file; Use vectors to remember the header file vector; Last element of vectors, back()

#include <iostream>
#include <vector>

using namespace std;

vector<int> nums;

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

int main()
{
    int n, b;
    cin >> n >> b;
    
    if (!n) nums.push_back(0);
    while (n) nums.push_back(n % b), n /= b;
    
    if (check()) puts("Yes");
    else puts("No");
    
    cout << nums.back();
    for (int i = nums.size() - 2; i >= 0; i -- ) cout << ' ' << nums[i];
    
    return 0;
}

1027 Colors in Mars (20 points)

• Title: Convert input decimal number to decimal number
• Thought: Note that the maximum decimal number entered here is 168, which means that there are at most two digits after conversion to decimal. This also can exactly solve the problem if only one digit must be added 0 to the left, that is to say, the output is a two-digit decimal number in any case; Notice this "get" way of converting decimal numbers to numbers greater than ten.
• Syntax: int to char

#include <iostream>

using namespace std;

int a[3];

char get(int x)
{
    if (x > 9) return 'A' + x - 10;
    return '0' + x;
}

int main()
{
    for (int i = 0; i < 3; i ++ ) cin >> a[i];
    
    cout << '#';
    
    for (int i = 0; i < 3; i ++ ) cout << get(a[i] / 13) << get(a[i] % 13);
    
    return 0;
}

1100 Mars Numbers (20 points)

• Idea: The important thing is that the English words in high and low digits are not duplicated, so they can be directly connected in the same array
• Syntax: stringstream header file is sstream

#include <iostream>
#include <sstream>

using namespace std;

char names[][5] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};

int get(string word)
{
    for (int i = 0; i < 25; i ++ )
        if (names[i] == word)
        {
            if (i < 13) return i;
            return 13 * (i - 12);
        }
    return -1;      // Must not execute
}

int main()
{
    int T;
    cin >> T;
    getchar();
    
    while (T -- )
    {
        string line;
        getline(cin, line);
        
        stringstream ssin(line);
        
        if (line[0] <= '9')
        {
            int v;
            ssin >> v;
            if (v < 13) cout << names[v] << endl;
            else
            {
                cout << names[12 + v / 13];
                if (v % 13 != 0) cout << " " << names[v % 13];
                cout << endl;
            }
        }
        else
        {
            string word;
            int res = 0;
            
            while (ssin >> word) res += get(word);
            cout << res << endl;
        }
    }
}