[PYTHON] Codeforces Round # 609 (Div. 2) (up to B)

Div2A. Equation

Answer two numbers such that the difference is $ n $. For a moment I thought about factoring the difference into $ n $ in order, but when I thought about it, it was a gag. If you answer $ 9n $ and $ 8n $, the difference will be $ n $ and both will be composite numbers.

python

n = int(input())
print(9*n,8*n)

C++

#include<bits/stdc++.h>
int main(){
    int n;
    std::cin >> n;
    std::cout << 9*n << " " << 8*n << std::endl;
}

Div2B. Modulo Equality

First of all, the problem statement is difficult to understand. It says what to do with the substitution $ p_n $ ... but in short

Given the sequences $ \ {a_i } $ and $ \ {b_i } $. The smallest $ x $ such that the sequence $ \ {a_i + x \ (\ mathrm {mod} \ m) } $ matches $ \ {b_i } $ ** appropriately sorted ** Answer.

Is the problem.

Now, the first thing that comes to mind with brain death is that you want to explore $ x $. Since we consider $ \ mathrm {mod} \ m $, we can equate the amount that exceeds $ m $ as $ x $. However, since the range of $ m $ is still $ 1 \ leq m \ leq 10 ^ 9 $, it is impossible in time to search the entire range.

Another constraint is that $ 1 \ leq n \ leq 2000 $, that is, the sequences $ a $ and $ b $ can be up to 2000 in size. In fact, this is important, and the policy of searching all $ x $ can be left as it is to reduce the scope of investigation. At least one of the elements of ** ʻa [i] + xmust beb [0] so that the addition of x to ʻa and the appropriately rearranged version of b match. Must match **.

Therefore, let's thoroughly search which of ʻacorresponds tob [0]` and output the smallest one that satisfies the condition. Specifically, please refer to the code below.

Python

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    b.sort()
    answer = []
    for i in range(n):
        x = (b[0] - a[i]) % m  # b[0]And a[i]Determine x so that
        tmp = list(map(lambda num: (num + x) % m, a))
        tmp.sort()
        if tmp == b:
            answer.append(x)
    print(min(answer))
    return

if __name__ == '__main__':
    main()

C++

#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<int> a(n), b(n);
    rep(i, n) scanf("%d", &a[i]);
    rep(i, n) scanf("%d", &b[i]);
    std::sort(begin(b), end(b));
    std::vector<int> ans;
    rep(i, n) {
        int x = (b[0] - a[i] + m) % m;
        std::vector<int> tmp(n);
        std::transform(begin(a), end(a), begin(tmp), [&](intnum){return(num+x)%m;});
        std::sort(begin(tmp), end(tmp));
        if(tmp == b) {
            ans.emplace_back(x);
        }
    }
    std::sort(begin(ans), end(ans));
    printf("%d\n", ans[0]);
}

int main() {
    solve();
    return 0;
}