计数器

[编程题]计数器

热度指数：3826 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小爱有一个奇怪的计数器。在第一个时刻计数器显示数字3，在接下来的每一个时刻，屏幕上的数字都会减1，直到减到1为止。

接下来，计数器会重置为上一个计数周期初始值的两倍，然后再每一个时刻减1。具体过程如下图所示：

找出规律，并打印出t时刻计数器的值。

输入描述:

输入为时刻t，一个整形数字。0<t<1e12

输出描述:

计数器显示的值。

示例1

输入

输出

算法知识视频讲解

Python3

TS9527

找规律可以得到答案的数学公式。

首先，以这个计数器一次循环作为一组，可以发现对于第 $i$ 轮循环，这个计数器会跳过的数字的数量是 $a_i = 3\cdot2^{i - 1}$ 。那么，跳完了第 $j$ 组的所有数字后，这个计数器总共跳过的数字数量由等比数列求和公式可以得到是 $S_j = \Sigma_{i = 1}^{j}a_i = 3(2^j - 1)$ 。

现在，我们希望求得第 $t$ 个数的数值，就需要确定第 $t$ 步所在的组。我们前面已经跳过了 $k$ 组，那么应有 $3(2^k - 1) < t$ ，可以解得 $k < \log_2(\frac{t}{3} + 1)$ 。显然， $k$ 为一个整数，因此取 $k = \lfloor\log_2(\frac{t}{3} + 1)\rfloor$ 。这里需要特别注意的是，当 $\log_2(\frac{t}{3} + 1)$ 为整数的时候，这个解应该减1才能满足小于条件（因为向下取整不会取到比这个整数小）。不过，我们可以发现，当 $t$ 满足这个情况的时候，计数器的值为1，因此可以直接输出1。

现在我们知道前面跳了 $k$ 组了，那么计数器在第 $t$ 时刻就在第 $k + 1$ 组。第 $k + 1$ 组的起始数值为 $3\cdot2^{k + 1 - 1} = 3\cdot2^k$ 。前面 $k$ 组已经占用的时刻数，也就是跳过的数量为 $3(2^k - 1)$ ，因此要跳到第 $t$ 时刻还要再跳 $t - 3(2^k - 1) - 1$ 次。跳完这么多次后计数器上显示的数值，也就是答案，为 $3\cdot2^k - [t - 3(2^k - 1) - 1]$ 。

AC代码：

import math


class MainActivity:

    def main(self):
        # Read the data
        t = int(input())
        # Calculate the result
        k = math.log2(t / 3 + 1)
        if math.floor(k) == k:
            print(1)
            return
        k = math.floor(k)
        result = 3 * 2 ** k - (t - 3 * (2 ** k - 1)) + 1
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-02 16:23:38 回复(0)