艰难的第一天

题目描述

病毒第 1 分钟占用 $x$ MB，之后每分钟占用量变为上一分钟的 $y$ 倍；内存剩余 $4\text{GB}=4096\text{MB}$ ，占用量等于 4096 就算占满，求第几分钟占满。输入一行两个实数 $x,\ y$ （ $0<x\leqslant 1000,\ 1<y\leqslant 10$ ），输出一个整数表示分钟数。样例：输入 32 2 输出 8；输入 2 1.5 输出 20。

思路

第 $n$ 分钟占用量为 $x\cdot y^{\,n-1}$ ，要求最小 $n$ 使 $x\cdot y^{\,n-1}\geqslant 4096$ ；两边取对数得 $n-1\geqslant \ln(4096/x)/\ln y$ ，上取整再 $+1$ 即为答案。浮点对数只当估计，再用高精度乘法在估计值附近双向修正，保证“恰好等于 4096 即占满”的临界判对。

参考代码

Python 版：

python

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
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 19:18
# update_at: 2026-10-02 19:18

import math
import sys
from fractions import Fraction

FULL = Fraction(4096)  # 内存占满阈值：4GB = 4096MB


def solve() -> None:
    x_s, y_s = sys.stdin.read().split()
    xf, yf = float(x_s), float(y_s)

    # 浮点对数只做初始估计：求最小 m 使 x·y^m ≥ 4096（第 m+1 分钟占满）
    m = max(0, math.ceil(math.log(4096 / xf) / math.log(yf) - 1e-9))

    # 用精确有理数校验边界（等号成立的临界靠它判定），把估计值收敛到真正的最小 m
    x, y = Fraction(x_s), Fraction(y_s)
    while m > 0 and x * y ** (m - 1) >= FULL:
        m -= 1
    while x * y ** m < FULL:
        m += 1

    print(m + 1)  # 第 1 分钟占用 x，占满发生在第 m+1 分钟


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 02:05
 * update_at: 2026-10-06 02:07
 */
// main.cpp：对数闭式解求病毒首次占满 4096MB 的分钟数。
#include <cmath>
#include <iostream>
using namespace std;

typedef long long ll;

long double x; // 病毒第 1 分钟占用的内存，单位 MB
long double y; // 每分钟占用量增长为上一分钟的 y 倍

// 判断第 n 分钟的占用量 x·y^(n-1) 是否已达到 4096MB。
bool reached(ll n) {
    return x * powl(y, n - 1) >= 4096.0L;
}

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

    cin >> x >> y;

    // 由 x·y^(n-1) >= 4096 取对数，估计 m = n-1 的上取整；减 1e-9 吸收浮点超调
    ll m = ceill(logl(4096.0L / x) / logl(y) - 1e-9L);
    if (m < 0) {
        m = 0;
    }

    // 在估计值附近用高精度乘法复核，保证“恰好等于 4096 即占满”的临界判对
    while (m > 0 && reached(m)) { // 第 m 分钟就已占满，说明估计偏大
        m--;
    }
    while (!reached(m + 1)) { // 第 m+1 分钟还没占满，继续后移
        m++;
    }

    cout << m + 1 << endl; // 第 1 分钟占用 x，占满发生在第 m+1 分钟
    return 0;
}

目录

题目描述

思路

参考代码