2023 小苹果 · 方案二只盯住两个数字

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1024 字

跟踪剩余个数和目标苹果的当前序号

2023
模拟

正文

// CSP-J 2023 复赛 T1 · 小苹果（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2023A
//
// 方案二 · 只盯住两个数字（O(log n)）
// 完全不需要真的摆出所有苹果，只要一直跟踪两件事：
//   cnt —— 现在还剩几个苹果；
//   idx —— 编号为 n 的那个苹果，现在是第几个。
// 每天被拿走的是第 1、4、7、... 个，它们的共同点是「除以 3 余 1」。
//   所以：idx % 3 == 1 就说明编号 n 在今天被拿走了；
//   每天拿走的总数是 ceil(cnt / 3)，剩下 cnt - (cnt + 2) / 3 个；
//   编号 n 前面被拿走了 ceil((idx - 1) / 3) = (idx + 1) / 3 个，所以新下标是 idx - (idx + 1) / 3。
// 苹果数每天大约变成原来的三分之二，所以最多几十天就结束，完全不用怕 n = 1e9。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);

    int n;
    cin >> n;

    int cnt = n;      // 剩余苹果数
    int idx = n;      // 编号 n 现在排在第几个
    int day = 0;
    int when = 0;

    while (cnt > 0) {
        day++;
        if (when == 0 && idx % 3 == 1) when = day;   // 今天轮到它了
        cnt -= (cnt + 2) / 3;                        // 拿走 ceil(cnt / 3) 个
        idx -= (idx + 1) / 3;                        // 它前面被拿走的个数
    }
    cout << day << " " << when << "\n";
    return 0;
}

2023 小苹果 · 方案二 只盯住两个数字

正文

CSP-J 标程 · 复赛真题的其它内容

2023 小苹果 · 方案二只盯住两个数字