oj.uz

Submission #440803

# Submission time Handle Problem Language Result Execution time Memory
440803 2021-07-03T07:59:23 Z prvocislo PIN (CEOI10_pin) C++17
100 / 100
 558 ms 14772 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 972 KB Output is correct
2 Correct 9 ms 976 KB Output is correct
3 Correct 6 ms 824 KB Output is correct
4 Correct 101 ms 3240 KB Output is correct
5 Correct 155 ms 3688 KB Output is correct
6 Correct 154 ms 3716 KB Output is correct
7 Correct 102 ms 3240 KB Output is correct
8 Correct 131 ms 3880 KB Output is correct
9 Correct 239 ms 5408 KB Output is correct
10 Correct 300 ms 5784 KB Output is correct
11 Correct 153 ms 3892 KB Output is correct
12 Correct 369 ms 5532 KB Output is correct
13 Correct 165 ms 4252 KB Output is correct
14 Correct 169 ms 3840 KB Output is correct
15 Correct 334 ms 5612 KB Output is correct
16 Correct 365 ms 11112 KB Output is correct
17 Correct 525 ms 14772 KB Output is correct
18 Correct 399 ms 12244 KB Output is correct
19 Correct 517 ms 13560 KB Output is correct
20 Correct 558 ms 14744 KB Output is correct