Submission #440803

#	Time	Username	Problem	Language	Result	Execution time	Memory
440803		prvocislo	PIN (CEOI10_pin)	C++17	100 / 100	558 ms	14772 KiB

pin

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

ll c(int n, int k)
{
    int x = 1;
    for (int i = 1; i <= n; i++) x *= i;
    for (int i = 1; i <= k; i++) x /= i;
    for (int i = 1; i <= n-k; i++) x /= i;
    return x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, d;
    cin >> n >> d;
    map<string, int> m; // * je wildcard
    vector<ll> v(5, 0); // v[x] = pocet cisel ktore maju (aspon) x cifier rovnakych
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int msk = 0; msk < (1 << 4); msk++)
        {
            string s2 = s;
            for (int j = 0; j < 4; j++) if (msk & (1 << j)) s2[j] = '*';
            m[s2]++;
        }
    }
    for (const pair<string, int> &i : m)
    {
        int same = 4 - count(i.first.begin(), i.first.end(), '*');
        v[same] += i.second * 1ll * (i.second - 1) / 2;
    }
    for (int i = 4; i >= 0; i--)
    {
        for (int j = i + 1; j <= 4; j++)
        {
            v[i] -= c(j, i) * v[j];
        }
    }
    cout << v[4 - d] << "\n";
    return 0;
}

• Subtask 1: 100 / 100