Codeforces

A. Add and Divide

You have two positive integers $a$ and $b$.

You can perform two kinds of operations:

• $a=⌊{\frac{a}{b}}⌋$ (replace $a$ with the integer part of the division between $a$ and $b$)
• $b=b+1$ (increase $b$ by $1$)

Find the minimum number of operations required to make $a = 0$.

Input

The first line contains a single integer $t$ $(1≤t≤100)$ — the number of test cases.

The only line of the description of each test case contains two integers $a,b$ $(1≤a,b≤10^9)$.

Output

For each test case, print a single integer: the minimum number of operations required to make $a=0$.

풀이

b에서 1을 몇번 더할지 먼저 정하고 나눈다. 1e9를 2로 나누어도 30번밖에 안되기 때문에 TLE가 뜨지 않는다. ans값을 하나 구했을때 b를 ans번 보다 많이 더할 필요가 없기 때문에 for문에서 i를 ans이하로 해두고 ans를 계속 갱신하며 정답을 찾는다. b가 1일때는 1을 더하고 시작한다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int a, b; cin >> a >> b;
    int ans = 1e9;
    for (int i = 0; i < ans; i++) {
        if (b + i == 1) continue;
        int cnt = i;
        int tmp_a = a;
        while (tmp_a > 0) {
            tmp_a /= b + i;
            cnt++;
        }
        ans = min(ans, cnt);
    }
    cout << ans << "\n";
}

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

B. Replace and Keep Sorted

Given a positive integer $k$, two arrays are called $k$-similar if:

• they are strictly increasing;
• they have the same length;
• all their elements are positive integers between $1$ and $k$ (inclusive);
• they differ in exactly one position.

You are given an integer $k$, a strictly increasing array $a$ and $q$ queries. For each query, you are given two integers ${l_i}\le{r_i}$. Your task is to find how many arrays $b$ exist, such that $b$ is $k$-similar to array $[a_{l_i},a_{l_{i+1}}…,a_{r_i}]$.

Input

The first line contains three integers $n$, $q$ and $k$ $(1≤n,q≤10^5, n≤k≤10^9)$ — the length of array $a$, the number of queries and number $k$.

The second line contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤k)$. This array is strictly increasing — $a_1 < a_2 < … < a_n$.

Each of the following $q$ lines contains two integers $l_i, r_i$ $(1≤l_i≤r_i≤n)$.

Output

Print $q$ lines. The $i$-th of them should contain the answer to the $i$-th query.

풀이

순열의 각 인덱스에서 가능한 숫자를 센다. 이때 부분 순열에서 주어진 배열의 값은 나올 수 없고, 양 끝에 있는 수의 경우 한번, 사이에 있는 수의 경우 두번 나온다. 따라서 0번 나오는 수(n_zeros)는 $l$에서 $r$까지의 숫자 수, 한번 나오는 수(n_ones)는 1부터 부분순열의 시작, $k$부터 부분순열의 끝까지의 숫자 수, 두번 나오는 수(n_twos)는 $k$에서 0번, 한번 나오는 수를 빼면 된다.

결과는 (n_ones + n_twos * 2) 이다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int a[100001];
int n, q, k;

void solve() {
    int l, r; cin >> l >> r;
    int n_zeros = r - l + 1;
    int n_ones = a[l] - 1 + k - a[r];
    int n_twos = k - n_zeros - n_ones;
    cout << n_ones + n_twos * 2 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (q--) solve();
    return 0;
}

https://codeforces.com/contest/1485