Codeforces

A. GCD Sum

The $𝑔𝑐𝑑𝑆𝑢𝑚$ of a positive integer is the $𝑔𝑐𝑑$ of that integer with its sum of digits. Formally, $𝑔𝑐𝑑𝑆𝑢𝑚(𝑥)=𝑔𝑐𝑑$($𝑥$, sum of digits of $𝑥$) for a positive integer $𝑥$. $𝑔𝑐𝑑(𝑎,𝑏)$ denotes the greatest common divisor of $𝑎$ and $𝑏$ — the largest integer $𝑑$ such that both integers $𝑎$ and $𝑏$ are divisible by $𝑑$.

For example: $𝑔𝑐𝑑𝑆𝑢𝑚(762)=𝑔𝑐𝑑(762,7+6+2)=𝑔𝑐𝑑(762,15)=3$.

Given an integer $𝑛$, find the smallest integer $𝑥≥𝑛$ such that $𝑔𝑐𝑑𝑆𝑢𝑚(𝑥)>1$.

Input

The first line of input contains one integer $𝑡$ $(1≤𝑡≤10^4)$ — the number of test cases.

Then $𝑡$ lines follow, each containing a single integer $𝑛$ $(1≤𝑛≤10^{18})$.

All test cases in one test are different.

Output

Output $𝑡$ lines, where the $𝑖$-th line is a single integer containing the answer to the $𝑖$-th test case.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void solve() {
    ll n1; cin >> n1;
    ll gcd_n = 1;
    while (gcd_n == 1) {
        ll tmp = n1, n2 = 0;
        while (tmp > 0) {
            n2 += tmp % 10;
            tmp /= 10;
        }
        gcd_n = gcd(n1, n2);
        if (gcd_n == 1) n1++;
    }
    cout << n1 << "\n";
}

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

B. Box Fitting

You are given $𝑛$ rectangles, each of height $1$. Each rectangle’s width is a power of $2$ (i. e. it can be represented as $2^𝑥$ for some non-negative integer $𝑥$).

You are also given a two-dimensional box of width $𝑊$. Note that $𝑊$ may or may not be a power of $2$. Moreover, $𝑊$ is at least as large as the width of the largest rectangle.

You have to find the smallest height of this box, such that it is able to fit all the given rectangles. It is allowed to have some empty space left in this box after fitting all the rectangles.

You cannot rotate the given rectangles to make them fit into the box. Moreover, any two distinct rectangles must not overlap, i. e., any two distinct rectangles must have zero intersection area.

See notes for visual explanation of sample input.

Input

The first line of input contains one integer $𝑡$ $(1≤𝑡≤5⋅10^3)$ — the number of test cases. Each test case consists of two lines.

For each test case:

• the first line contains two integers $𝑛$ $(1≤𝑛≤10^5)$ and $𝑊$ $(1≤𝑊≤10^9)$;
• the second line contains 𝑛 integers $𝑤_1,𝑤_2,…,𝑤_𝑛$ $(1≤𝑤_𝑖≤10^6)$, where 𝑤𝑖 is the width of the $𝑖$-th rectangle. Each $𝑤_𝑖$ is a power of $2$;
• additionally, $max_{𝑖=1}^𝑛 𝑤_𝑖≤𝑊$.

Output

Output $𝑡$ integers. The $𝑖$-th integer should be equal to the answer to the $𝑖$-th test case — the smallest height of the box.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int A[21];

bool chkEmpty() {
    if (all_of(A, A + 21, [](int i){ return i == 0; })) return true;
    return false;
}

void solve() {
    memset(A, 0, sizeof(A));
    int n, W; cin >> n >> W;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        int tmp = 0;
        while (a > 0) { tmp++; a /= 2; }
        A[tmp]++;
    }
    int cnt = 0;
    while (!chkEmpty()) {
        int tmp = W;
        for (int i = 21; i >= 1; i--) {
            while (A[i] > 0 && tmp > 0) {
                int k = 1;
                for (int j = 0; j < i - 1; j++) k *= 2;
                if (tmp - k < 0) break;
                tmp -= k;
                A[i]--;
            }
        }
        cnt++;
    }
    cout << cnt << "\n";
}

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

C. Planar Reflections

Gaurang has grown up in a mystical universe. He is faced by 𝑛 consecutive 2D planes. He shoots a particle of decay age $𝑘$ at the planes.

A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age $𝑘−1$. If a particle has decay age equal to $1$, it will NOT produce a copy.

For example, if there are two planes and a particle is shot with decay age $3$ (towards the right), the process is as follows: (here, $𝐷(𝑥)$ refers to a single particle with decay age $𝑥$)

1. the first plane produces a $𝐷(2)$ to the left and lets $𝐷(3)$ continue on to the right;
2. the second plane produces a $𝐷(2)$ to the left and lets $𝐷(3)$ continue on to the right;
3. the first plane lets $𝐷(2)$ continue on to the left and produces a $𝐷(1)$ to the right;
4. the second plane lets $𝐷(1)$ continue on to the right ($𝐷(1)$ cannot produce any copies).

In total, the final multiset $𝑆$ of particles is ${𝐷(3),𝐷(2),𝐷(2),𝐷(1)}$. (See notes for visual explanation of this test case.)

Gaurang is unable to cope up with the complexity of this situation when the number of planes is too large. Help Gaurang find the size of the multiset $𝑆$, given $𝑛$ and $𝑘$.

Since the size of the multiset can be very large, you have to output it modulo $10^9+7$.

Note: Particles can go back and forth between the planes without colliding with each other.

Input

The first line of the input contains the number of test cases $𝑡$ $(1≤𝑡≤100)$. Then, $𝑡$ lines follow, each containing two integers $𝑛$ and $𝑘$ $(1≤𝑛,𝑘≤1000)$.

Additionally, the sum of $𝑛$ over all test cases will not exceed $1000$, and the sum of $𝑘$ over all test cases will not exceed $1000$. All test cases in one test are different.

Output

Output $𝑡$ integers. The $𝑖$-th of them should be equal to the answer to the $𝑖$-th test case.

풀이

DP - Memoization (Top-Down)

코드

#include <bits/stdc++.h>

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

int N, K;
int cache[1001][1001];

int f(int l, int k) {
    if(l == N || k == 1) return 1;
    int& ret = cache[l][k];
    if(ret != -1) return ret;
    return ret = (f(N - l, k - 1) + f(l + 1, k)) % MOD;
}
void solve() {
    cin >> N >> K;
    memset(dp, -1, sizeof(dp));
    cout << f(0, K) << nl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

https://codeforces.com/contest/1498