2022年の春、京東のフロントエンドの筆記試験問題の復習

京東の筆記試験問題の復習、フロントエンド開発の筆記試験問題で、選択問題 30 問と 2 つのプログラミング問題が含まれています（360 と同じ日に行われました）。

選択問題（30 問）#

データベース、高等数学、方程式など、すべての内容が含まれていますが、後半は主にフロントエンドの問題です。

プログラミング問題 - 1 小明の最大値（AC100%）#

小明は一台の機械を持っており、数を入力すると非負の整数が返されます。小明は何度も試行した結果、この機械に数 x を与えると、機械はその数を P で割った余り y を返すことを知りました。P は機械の下に刻まれており、小明はそれを確認できます。

例えば、P=5 の場合、x=9 を入力すると機械は 4 を返し、15 を入力すると 0 を返します。

小明は現在、[L,R] という閉区間内のすべての整数を入力することができます。小明がこの機械から得られる最大の返り値はいくつかを求めています。

入力の説明
複数のテストケースがあります。最初の行にはテストケースの数 T が与えられます。

次の 3 行には、それぞれ T 個の整数 L [i]、R [i]、P [i] があります。L [i]、R [i]、P [i] は、i 番目のテストケースの区間の左端、右端、および機械のパラメータ P を表します。

出力の説明
1 行に T 個の数を出力し、それぞれの数は順番に各テストケースの答えを表します。

入力例

出力例

1 2

ヒント
最初のテストケースでは、入力 5 は 0 を返し、入力 6 は 1 を返すため、答えは 1 です。

2 番目のテストケースでは、入力 1 は 1 を返し、入力 2 は 2 を返すため、答えは 2 です。

アプローチ#

明らかなことですが、問題の意味は L~R の範囲内で x を見つけることです。そして、 x%p が最大になるかどうかを判断します。まず、 L/p が R/p と等しいかどうかを確認し、等しい場合は確実に R%p です。そうでなければ、既に一周余っているはずなので、最大の余りは p-1 です。

コード#

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 70005;
int T;
int L[maxn], R[maxn], P[maxn];
vector<int> ans;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    for(int i = 0; i < T; ++i) 
        cin >> L[i];
    for(int i = 0; i < T; ++i) 
        cin >> R[i];
    for(int i = 0; i < T; ++i) 
        cin >> P[i];
    for(int i = 0; i < T; ++i) {
        int l = L[i], r = R[i], p = P[i];
        if(l/p == r/p) ans.push_back(r%p);
        else ans.push_back(p-1);
        
    }
    for(int i = 0; i < T; ++i) {
        if(i == 0) cout << ans[i];
        else cout << ' ' << ans[i];
    }
    cout << endl;
    return 0;
}

プログラミング問題 - 2 鶏卵を分ける（AC 73%）#

言葉で言うと：
初期値 x
次の 2 つの操作が可能です：

++x
if(x%3 == 0) x /= 3
x を y にするために最小限のステップ数は何ですか？
いくつかのテストケースを用意しました。

例 1

10
5
4

例 2

例 3

4
299 298
31 100
8 1
900100000000000000 20000200000100000

200
69
3
8887854321087664

さて、分析を始めましょう。

アプローチ#

できるだけ x/=3 を行い、x/3 が y より小さい場合は、目標数に加えます。
x/=3 後、3 で割り切れず、かつ y より大きい場合は、1〜3 を加えて 3 で割り切れるようにします。
最後に、TLE ではなく WA になりました。どこにまだ境界の問題があるかはわかりませんが、73% を通過しました。

コード#

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 70005;
typedef long long ll;
int T;
ll x, y;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> x >> y;
        ll cnt = 0;
        while(x != y) { 
            while (x != y && x % 3 == 0 && x/3 >= y) {
                x /= 3;
                ++cnt;
            }
            if(x == y) break;

            if(x % 3 == 0) x /= 3,++cnt;
            if(x < y) { // 加到目标数
                cnt += y-x;
                break;
            } else {
                while(x != y && x % 3 != 0) {   // 最多加三次
                    ++x, ++cnt;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}