[PYTHON] Codeforces Round # 609 (Div.2) (jusqu'à B)

Div2A. Equation

Répondez à deux nombres tels que la différence soit $ n $. Pendant un moment, j'ai pensé à factoriser la différence en $ n $ dans l'ordre, mais quand j'y ai pensé, c'était un bâillon. Si vous répondez 9n $ et 8n $, la différence sera de $ n $ et les deux seront des nombres composites.

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

Tout d'abord, l'énoncé du problème est difficile à comprendre. Il dit quoi faire avec le remplacement $ p_n $, mais en bref

Etant donné la séquence $ \ {a_i } $ et $ \ {b_i } $. Le minimum $ x $ tel que la séquence $ \ {a_i + x \ (\ mathrm {mod} \ m) } $ correspond à $ \ {b_i } $ ** triée de manière appropriée ** Répondre.

C'est le problème.

Maintenant, la première chose qui vous vient à l'esprit avec la mort cérébrale est que vous voulez explorer $ x $. Puisque nous considérons $ \ mathrm {mod} \ m $, nous pouvons assimiler le montant qui dépasse $ m $ à $ x $. Cependant, puisque la plage de $ m $ est toujours $ 1 \ leq m \ leq 10 ^ 9 $, il est impossible à temps de rechercher la plage entière.

Une autre contrainte est que $ 1 \ leq n \ leq 2000 $, c'est-à-dire que les colonnes $ a $ et $ b $ peuvent avoir une taille allant jusqu'à 2000. En fait, c'est important, et la politique de recherche de tous les $ x $ peut être laissée telle quelle pour réduire la portée de l'enquête. Au moins un des éléments de ** ʻa [i] + x` doit être "b [0]" pour que l'addition de x à "a" et le réarrangement approprié de "b" correspondent. Doit correspondre **.

Par conséquent, recherchons tous les «a» correspondant à «b [0]» et sortons le plus petit qui satisfait la condition. Plus précisément, veuillez vous référer au code ci-dessous.

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]Et un[i]Déterminez x pour que
        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;
}