AtCoder Beginner Contest 336

[ABC336A] Long Loong

题面翻译

给定一个数 \(n\)，请输出一个由一个 L、\(n\) 个 o 、一个 n 和一个 g 组成的字符串（区分大小写）。

题目描述

正の整数 $ X $ について、レベル $ X $ の 龍文字列 とは、$ 1 $ 個の L, $ X $ 個の o, $ 1 $ 個の n, $ 1 $ 個の g をこの順に並べた長さ $ (X+3) $ の文字列です。

正の整数 $ N $ が与えられるので、レベル $ N $ の龍文字列を出力してください。
大文字と小文字は区別されることに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

レベル $ N $ の龍文字列を出力せよ。

样例 #1

样例输入 #1

1
3

样例输出 #1

1
Looong

样例 #2

样例输入 #2

1
1

样例输出 #2

1
Long

提示

制約

  • $ 1 N 2024 $
  • $ N $ は整数

Sample Explanation 1

$ 1 $ 個の L, $ 3 $ 個の o, $ 1 $ 個の n, $ 1 $ 個の g をこの順に並べた文字列は Looong です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 模拟
#include <bits/stdc++.h>
using namespace std;

int main()
{
    cout << "L";
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cout << "o";
    cout << "ng";
    return 0;
}
-------------------------------------
    #include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    cout << "L" << string(n, 'o') << "ng" << '\n';
    return 0;
}

[ABC336B] CTZ

题面翻译

求一个正整数 \(N\) 二进制下末尾 \(0\) 的个数。

\(1\le N\le 10^9\)。

题目描述

正の整数 $ X $ に対して、$ X $ を $ 2 $ 進表記したときに 末尾 に連続する $ 0 $ の個数（の最大値）を $ (X) $ で表します。
ただし、$ X $ を $ 2 $ 進表記したとき末尾が $ 1 $ ならば $ (X)=0 $ です。

正の整数 $ N $ が与えられるので、$ (N) $ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

$ (N) $ を出力せよ。

样例 #1

样例输入 #1

1
2024

样例输出 #1

1
3

样例 #2

样例输入 #2

1
18

样例输出 #2

1
1

样例 #3

样例输入 #3

1
5

样例输出 #3

1
0

提示

制約

  • $ 1 N 10^9 $
  • $ N $ は整数

Sample Explanation 1

$ 2024 $ を $ 2 $ 進表記すると 11111101000 であり、末尾から 0 が $ 3 $ 個連続しているため、$ (2024)=3 $ です。 よって、$ 3 $ を出力します。

Sample Explanation 2

$ 18 $ を $ 2 $ 進表記すると 10010 であるため、$ (18)=1 $ です。 0 は末尾から連続する必要があることに注意してください。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//模拟
//每次丢一位
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, c = 0;
    cin >> n;
    while (n)
    {
        if (n % 2 == 0)
            c++;
        else
            break;
        n /= 2;
    }
    cout << c;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//内置函数
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x;
    cin >> x;
    cout << __builtin_ctz(x) << '\n';

    return 0;
}

[ABC336C] Even Digits

题面翻译

定义满足没有前导零，且十进制下每个数位都为偶数的非负整数为好数。

求第 \(N\) 小的好数。\(1\le N\le 10^{12}\)。

题目描述

非負整数 $ n $ が次の条件を満たすとき、$ n $ を 良い整数 と呼びます。

  • $ n $ を $ 10 $ 進法で表したときに、偶数の数字 $ (0, 2, 4, 6, 8) $ のみが登場する。

例えば $ 0 \(、\) 68 $ および $ 2024 $ は良い整数です。

整数 $ N $ が与えられます。良い整数のうち小さい方から $ N $ 番目の整数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

小さい方から $ N $ 番目の良い整数を出力せよ。

样例 #1

样例输入 #1

1
8

样例输出 #1

1
24

样例 #2

样例输入 #2

1
133

样例输出 #2

1
2024

样例 #3

样例输入 #3

1
31415926535

样例输出 #3

1
2006628868244228

提示

制約

  • $ 1  N  10^{12} $
  • $ N $ は整数

Sample Explanation 1

良い整数を小さい方から順に並べると $ 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, $ となります。 小さい方から $ 8 $ 番目の良い整数は $ 24 $ なので、これを出力します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//想起来是上学期舍友的五进制题目了（）
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n;
    cin >> n;
    --n;
    string ans;
    while (n)
    {
        ans += (n % 5) * 2 + '0';
        n /= 5;
    }
    reverse(ans.begin(), ans.end());
    if (ans.empty())
        ans = "0";
    cout << ans << '\n';
    return 0;
}

[ABC336D] Pyramid

题面翻译

对于正整数 \(k\)，一个大小为 \(k\) 的“金字塔数列”为一个长度为 \(2k-1\) 的数列，里面的数字依次为 \(1,2,3,\dots k-1,k,k-1,\dots 3,2,1\)。
现在给一个长度为 \(n\) 的数列 \(S\)，你可以进行以下操作任意次，使得数列最后变为一个“金字塔数列”：

  • 选择一个数 \(i(1 \le i \le n)\)，把 \(S_i\) 减少 \(1\)。
  • 删除整个数列的第一个或最后一个数字。

问最后生成的“金字塔数列”的最大的 \(k\) 是多少。

题目描述

正の整数 $ k $ について、サイズ $ k $ の ピラミッド数列 とは、長さ $ (2k-1) $ の数列であって各項の値が順に $ 1,2,,k-1,k,k-1,,2,1 $ であるようなものをさします。

長さ $ N $ の数列 $ A=(A_1,A_2,,A_N) $ が与えられます。
$ A $ に対して、次の操作のうち一方を選んで行うことを繰り返して ($ 0 $ 回でも良い) 得ることのできるピラミッド数列のサイズの最大値を求めてください。

  • 数列の項を $ 1 $ つ選び、その項の値を $ 1 $ 減少させる。
  • 先頭または末尾の項を削除する。

なお、問題の制約のもとで、操作を繰り返すことで必ず $ 1 $ 種類以上のピラミッド数列を得ることができることが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A_1 $ $ A_2 $ $ $ $ A_N $

输出格式

数列 $ A $ に問題文の操作を繰り返して得ることのできるピラミッド数列のサイズの最大値を出力せよ。

样例 #1

样例输入 #1

1
2
5
2 2 3 1 1

样例输出 #1

1
2

样例 #2

样例输入 #2

1
2
5
1 2 3 4 5

样例输出 #2

1
3

样例 #3

样例输入 #3

1
2
1
1000000000

样例输出 #3

1
1

提示

制約

  • $ 1 N 2 10^5 $
  • $ 1 A_i 10^9 $
  • 入力はすべて整数

Sample Explanation 1

$ A=(2,2,3,1,1) $ から始めて、 次のようにして数列 $ A $ からサイズ $ 2 $ のピラミッド数列を作る事ができます。 - 第 $ 3 $ 項を選び、$ 1 $ 減少させる。数列は $ A=(2,2,2,1,1) $ となる。 - 先頭を削除する。数列は $ A=(2,2,1,1) $ となる。 - 末尾を削除する。数列は $ A=(2,2,1) $ となる。 - 第 $ 1 $ 項を選び、$ 1 $ 減少させる。数列は $ A=(1,2,1) $ となる。 $ (1,2,1) $ はサイズ $ 2 $ のピラミッド数列です。 一方、どのように操作を行ってもサイズ $ 3 $ 以上のピラミッド数列を作ることはできないため $ 2 $ を出力します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, a[N], q[N], p[N];
signed main()
{
    cin>>n;
    for (int i = 1; i <= n; i++)
       cin>>a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        q[i] = min(q[i - 1] + 1, a[i]);
    for (int i = n; i >= 1; i--)
        p[i] = min(p[i + 1] + 1, a[i]);
    for (int i = 1; i <= n; i++)
        ans = max(min(p[i], q[i]), ans);
    cout<<ans;
    return 0;
}