Solutiosn non officielles du 12ème concours de programmatino de l'Université de Technologie de Harbin (synchronisé)

A. Coupe de ciboulette

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, N = 1e5 + 5;
ll a[N];

inline ll puissanceRapide(ll x, ll y) {
    ll result = 1;
    while (y) {
        if (y & 1)
            result = (result * x) % mod;
        y >>= 1;
        x = (x * x) % mod;
    }
    return result;
}

ll inverseModulaire(ll a, ll b) {
    return (a * puissanceRapide(b, mod - 2)) % mod;
}

int main() {
    IOS;
    int t;
    cin >> t;

    a[0] = 1;
    for (int i = 1; i <= N; i++)
        a[i] = (a[i - 1] * i) % mod;

    while (t--) {
        ll n, m, k, q;
        cin >> n >> m >> k >> q;

        if (k > n) {
            cout << 0 << endl;
            continue;
        }

        ll dx = inverseModulaire(a[n], a[n - k]) % mod;
        ll dy = inverseModulaire(a[n + m], a[n + m - k]) % mod;
        dx = puissanceRapide(dx, q) % mod;
        dy = puissanceRapide(dy, q) % mod;

        ll resultat = inverseModulaire(dx, dy) % mod;

        cout << resultat % mod << endl;
    }
}

C. Labyrinthe

D. Voyage en montagne de gk

E. Chaîne de caractères de gk

Code

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
const int N = 1e6 + 5;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        s = ' ' + s;
        int n = s.size();

        for (int i = 1; i < n; i++) {
            if (s[i] == '?') {
                for (int j = 0; j < 26; j++) {
                    if (s[i - 1] != (char)(j + 'a') && s[i + 1] != (char)(j + 'a')) {
                        s[i] = (char)(j + 'a');
                        break;
                    }
                }
            }
        }

        for (int j = 0; j < 26; j++) {
            if (s[n - 1] != (char)(j + 'a'))
                s[n] = (char)(j + 'a');
        }

        cout << s.substr(1) << endl;
    }
}

F. Arbre de gk

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
const int N = 100000 + 5;
int n, k, ans = 0;
bool vis[N];
vector<int> v[N];

int dfs(int u) {
    int degre = v[u].size();
    for (auto i : v[u]) {
        if (vis[i])
            continue;
        vis[i] = true;
        degre -= dfs(i);
    }
    if (degre <= k)
        return 0;
    ans += degre - k;
    return 1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ans = 0;
        memset(vis, false, sizeof vis);
        cin >> n >> k;

        for (int i = 1; i < n; i++) {
            int u, x;
            cin >> u >> x;
            v[x].push_back(u);
            v[u].push_back(x);
        }

        vis[1] = true;
        dfs(1);
        cout << ans << endl;

        for (int i = 0; i <= n; i++)
            v[i].clear();
    }
}

G. Jeu de nombres de gk

Codde

#include <iostream>
#include <algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

int main() {
    IOS;
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 0 || m == 0) {
            cout << 0 << endl;
            continue;
        }

        int compteur = 0;
        while (m && n) {
            if (n < m) {
                compteur += m / n;
                m %= n;
            } else {
                compteur += n / m;
                n %= m;
            }
        }

        cout << compteur << endl;
    }
}

I. Encore une fois AK

Code

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[25] = {0}, b[25];
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);

        for (int i = 1; i <= n; i++)
            b[i] = a[i] - a[i - 1];
        sort(b + 1, b + n + 1);

        for (int i = 1; i <= n; i++)
            b[i] += b[i - 1];
        long long somme = 0;
        for (int i = 1; i <= n; i++)
            somme += b[i];
        cout << somme << endl;
    }
}

J. Multiplication de grands nombres

Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;
const int N = 100000 + 5;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long x, p;
        string s;
        int a[N];
        long long b[N];
        cin >> x >> s >> p;
        int n = s.size();

        long long resultat = 1;
        for (int i = n - 1; i >= 0; i--) {
            long long temp = x;
            for (int j = 1; j <= 9; j++) {
                if (j == s[i] - '0')
                    resultat = (resultat * x) % p;
                x = (temp * x) % p;
            }
        }

        cout << resultat << endl;
    }
}

K. Bombe rebondissante

L. NP-Hard

Code

#include

using namespace std;
int n;

int count(int q) {
int cnt = 0, tmp = n;
while (tmp) {
if (tmp % q == 1)
cnt++;
tmp /= q;
}
return cnt;
}

int main() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> n >> x >> y;
int xx = count(x), yy = count(y);
if (xx == yy)
cout << '=' << endl;
if (xx > yy)
cout << '>' << endl;
if (xx < yy)
cout << '<' << endl;
}
}