得物笔试得物笔试题 0525

笔试时间：2025年5月25日暑期实习

第一题

牛牛和牛牛妹来到了攀岩基地，他们选择了一处墙体作为攀岩地点，该面墙体，一共有 n 个踩踏点，从下至上依次编号为 1, 2, \ldots, n。

他们在工作人员的带领下领取了一个机械臂，使用一次这个机械臂，可以帮助使用者向上攀登，例如：假设牛牛当前位于第 i 号踩踏点，选择使用机械臂向上攀登 j 个踩踏点的高度，那么，牛牛就会到达第 i + j 号踩踏点。

由于机械臂的长度限制，使用者每一次攀登时选择的攀登高度 j 必须满足 1 \le j \le m。

将地面视为 0 号踩踏点，牛牛和牛牛妹初始位于地面上，他们想知道，如果在使用机械臂次数最少的前提下，该如何分配每次使用时向上攀登的踩踏点数量才能恰好到达第 n 个踩踏点呢？

牛牛和牛牛妹一筹莫展，于是向你提问，希望你回答这个问题，为了方便牛牛和牛牛妹理解，只需要你回答出字典序最小的攀登方案。

（注：字典序指的是两个方案依次进行比较，若比较到第一个不同的数值，值较小的那个方案的字典序较小；若某一个方案先比较完，则先比较完的方案字典序较小。）

输入描述

本题为多组测试数据，第一行输入一个正整数 T (1 \le T \le 1000)，代表测试数据组数。

接下去 T 行，每行两个正整数 n, m (5 \le n, m \le 1000)，分别代表踩踏点数量以及使用一次机械臂可以向上攀登的极限。

输出描述

对于每组测试数据，请在第一行输出最少需要使用机械臂的次数，第二行输出字典序最小的攀登方案。

样例输入

1

10 5

样例输出

2

5 5

说明：每次都使用机械臂攀登 5 个踩踏点，使用两次即可。

参考题解

C++：

// C++17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m;
        ll k = (n + m - 1) / m;
        ll rem = n - (k - 1) * m;

        cout << k << "\n";
        cout << rem;
        for (int i = 1; i < k; i++) {
            cout << " " << m;
        }
        cout << "\n";
    }

    return 0;
}

Java：

// Java 8+
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());
            long k = (n + m - 1) / m;
            long rem = n - (k - 1) * m;

            pw.println(k);
            pw.print(rem);
            for (int i = 1; i < k; i++) {
                pw.print(" ");
                pw.print(m);
            }
            pw.println();
        }
        pw.flush();
    }
}

Python：

sint = lambda: int(input())
mint = lambda: map(int, input().split())
lint = lambda: list(map(int, input().split()))

T = sint()
for _ in range(T):
    n, m = mint()
    k = (n + m - 1) // m
    rem = n - (k - 1) * m
    print(k)
    ans = [rem] + [m] * (k - 1)
    print(*ans)