Codeforces: Round #714 (Div.2)

2021-04-11

Codeforces

A. Array and Peaks

A sequence of $𝑛$ integers is called a permutation if it contains all integers from $1$ to $𝑛$ exactly once.

Given two integers $𝑛$ and $𝑘$ , construct a permutation $𝑎$ of numbers from $1$ to $𝑛$ which has exactly $𝑘$ peaks. An index $𝑖$ of an array $𝑎$ of size $𝑛$ is said to be a peak if $1<𝑖<𝑛$ and $𝑎_𝑖>𝑎_𝑖−1$ and $𝑎_𝑖>𝑎_𝑖+1$ . If such permutation is not possible, then print −1.

Input

The first line contains an integer $𝑡$ $(1≤𝑡≤100)$ — the number of test cases.

Then $𝑡$ lines follow, each containing two space-separated integers $𝑛$ $(1≤𝑛≤100)$ and $𝑘$ $(0≤𝑘≤𝑛)$ — the length of an array and the required number of peaks.

Output

Output $𝑡$ lines. For each test case, if there is no permutation with given length and number of peaks, then print $−1$ . Otherwise print a line containing $𝑛$ space-separated integers which forms a permutation of numbers from $1$ to $𝑛$ and contains exactly $𝑘$ peaks.

If there are multiple answers, print any.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

int A[110];

void solve() {
    int n, k; cin >> n >> k;
    memset(A, 0, sizeof(A));
    if ((n - 1) / 2 < k) { cout << "-1\n"; return; }
    int idx = 1, tmp = n;
    while (k--) {
        A[idx] = tmp--;
        idx += 2;
    }
    int p = 1;
    for (int i = 0; i < n; i++) {
        if (A[i] == 0) A[i] = p++;
    }
    for (int i = 0; i < n; i++) {
        cout << A[i] << " \n" [i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. AND Sequences

A sequence of $𝑛$ non-negative integers $(𝑛≥2)$ $𝑎_1,𝑎_2,…,𝑎_𝑛$ is called good if for all $𝑖$ from $1$ to $𝑛−1$ the following condition holds true:

$𝑎_1\&𝑎_2\&…\&𝑎_𝑖=𝑎_{𝑖+1}\&𝑎_{𝑖+2}\&…\&𝑎_𝑛,$

where $\&$ denotes the bitwise AND operation.

You are given an array $𝑎$ of size $𝑛$ $(𝑛≥2)$ . Find the number of permutations $𝑝$ of numbers ranging from $1$ to $𝑛$ , for which the sequence $𝑎_{𝑝_1}, 𝑎_{𝑝_2}, … ,𝑎_{𝑝_𝑛}$ is good. Since this number can be large, output it modulo $10^9+7$ .

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤10^4)$ , denoting the number of test cases.

The first line of each test case contains a single integer $𝑛$ $(2≤𝑛≤2⋅10^5)$ — the size of the array.

The second line of each test case contains $𝑛$ integers $𝑎_1,𝑎_2,…,𝑎_𝑛$ $(0≤𝑎_𝑖≤10^9)$ — the elements of the array.

It is guaranteed that the sum of $𝑛$ over all test cases doesn’t exceed $2⋅10^5$ .

Output

Output $𝑡$ lines, where the $𝑖$ -th line contains the number of good permutations in the $𝑖$ -th test case modulo $10^9+7$ .

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';
const int MOD = 1e9 + 7;

int A[200001];

void solve() {
    int n; cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) { cin >> A[i]; mp[A[i]]++; }
    vector<int> v;
    for (auto& it : mp) {
        if (it.second > 1) v.push_back(it.first);
    }
    if (v.empty()) { cout << "0\n"; return; }
    int mn = *min_element(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        if ((mn & A[i]) != mn) { cout << "0\n"; return; }
    }
    ll cnt = 1;
    int tmp = n - 2, k = n - mp[mn];
    while(k--) {
        cnt = (cnt * tmp) % MOD;
        tmp--;
    }
    for (int i = 1; i <= mp[mn]; i++) {
        cnt = (cnt * i) % MOD;
    }
    cout << cnt << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

C. Add One

You are given an integer $𝑛$ . You have to apply $𝑚$ operations to it.

In a single operation, you must replace every digit $𝑑$ of the number with the decimal representation of integer $𝑑+1$ . For example, $1912$ becomes $21023$ after applying the operation once.

You have to find the length of $𝑛$ after applying $𝑚$ operations. Since the answer can be very large, print it modulo $10^9+7$ .

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤2⋅10^5)$ — the number of test cases.

The only line of each test case contains two integers $𝑛$ $(1≤𝑛≤10^9)$ and $𝑚$ $(1≤𝑚≤2⋅10^5)$ — the initial number and the number of operations.

Output

For each test case output the length of the resulting number modulo $10^9+7$ .

풀이 1

DP - Tabulation (Bottom-Up)

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';
const int MOD = 1e9 + 7;

ll D[202020][10];

void solve() {
    int n, m; cin >> n >> m;
    ll ans = 0;
    while(n) {
        ans = (ans + D[m][n % 10]) % MOD;
        n /= 10;
    }
    cout << ans << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i = 0; i <= 9; i++) D[0][i] = 1;
    for(int i = 1; i <= 200000; i++) {
        for(int j = 0; j < 9; j++) {
            D[i][j] = D[i - 1][j + 1];
        }
        D[i][9] = (D[i - 1][0] + D[i - 1][1]) % MOD;
    }
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

풀이 2

DP - Memoization (Top-Down)

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';
const int MOD = 1e9 + 7;

ll D[202020][10];

ll f(int op, int first) {
    if (op == 0) return 1;
    ll& ret = D[op][first];
    if (ret != -1) return ret;
    if (first < 9) ret = f(op - 1, first + 1) % MOD;
    else ret = (f(op - 1, 0) + f(op - 1, 1)) % MOD;
    return ret;
}

void solve() {
    int n, m; cin >> n >> m;
    ll ans = 0;
    while(n) {
        ans = (ans + f(m, n % 10)) % MOD;
        n /= 10;
    }
    cout << ans << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    memset(D, -1, sizeof(D));
    while(t--) solve();
    return 0;
}

https://codeforces.com/contest/1513

 Codeforces: Round #713 (Div.3) PICNIC 