Codeforces: Round #714 (Div.2)
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;
}