[PYTHON] Codeforces Runde # 609 (Div. 2) (bis B)

Div2A. Equation

Beantworten Sie zwei Zahlen so, dass die Differenz $ n $ beträgt. Für einen Moment dachte ich darüber nach, den Unterschied in $ n $ zu zerlegen, aber als ich darüber nachdachte, war es ein Knebel. Wenn Sie $ 9n $ und $ 8n $ beantworten, beträgt die Differenz $ n $ und beide sind zusammengesetzte Zahlen.

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

Erstens ist die Problemstellung schwer zu verstehen. Es sagt, was mit dem Ersatz $ p_n $ zu tun ist, aber kurz gesagt

Gegeben die Reihenfolge $ \ {a_i } $ und $ \ {b_i } $. Das Minimum $ x $, so dass die Sequenz $ \ {a_i + x \ (\ mathrm {mod} \ m) } $ mit $ \ {b_i } $ ** übereinstimmt, entsprechend sortiert ** Antworten.

Ist das Problem.

Das erste, was Ihnen beim Hirntod einfällt, ist, dass Sie $ x $ erkunden möchten. Da wir $ \ mathrm {mod} \ m $ betrachten, können wir den Betrag, der $ m $ überschreitet, als $ x $ gleichsetzen. Da der Bereich von $ m $ jedoch immer noch $ 1 \ leq m \ leq 10 ^ 9 $ beträgt, ist es nicht möglich, den gesamten Bereich rechtzeitig zu durchsuchen.

Eine weitere Einschränkung besteht darin, dass $ 1 \ leq n \ leq 2000 $, dh die Spalten $ a $ und $ b $ können bis zu 2000 groß sein. Tatsächlich ist dies wichtig, und die Richtlinie zum Durchsuchen aller $ x $ kann beibehalten werden, und der Untersuchungsumfang kann reduziert werden. Mindestens eines der Elemente von ** a [i] + x muss b [0] sein, damit die Addition von x zu a und die entsprechende Umlagerung von b übereinstimmen. Muss passen **.

Lassen Sie uns daher gründlich suchen, welches von "a" "b [0]" entspricht, und das kleinste ausgeben, das die Bedingung erfüllt. Bitte beachten Sie insbesondere den folgenden Code.

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]Und ein[i]Bestimmen Sie x so, dass
        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;
}