主页 / 问题 / 1547728
Accepted
Nymos
Asked:2023-10-25 00:56:00 +0000 UTC2023-10-25 00:56:00 +0000 UTC

帮助优化Python问题“美丽的围巾”的程序

  • 772

大家好，我正在用Python解决一个问题。一切似乎都运行良好，但该网站因超出最长运行时间而给出 0 分。现在，当输入数据时，它显示48，而不是 。11任何人都可以帮助我，预先感谢！爱丽丝决定用一条漂亮的围巾来祝贺她的朋友新学年的开始。寒冷的秋天即将到来，她决定亲手为他织一条围巾。

在她的朋友不知情的情况下，爱丽丝得知他最喜欢 k 种不同的颜色。Alice决定织一条尺寸为n×m的围巾，围巾上不同颜色的条纹交替出现。她的朋友从来不走捷径，所以她觉得横条纹或竖条纹的围巾对他来说显得太“原始”。爱丽丝决定条纹绝对应该是对角的！

编织完一条围巾后，爱丽丝想起她的朋友认为其中一种颜色很特别！这就是颜色c，在他看来，这种颜色可以为学生在计算机科学奥林匹克竞赛中带来好运。爱丽丝对有多少围巾碎片具有这种颜色产生了极大的兴趣。围巾原来很大，爱丽丝织的时候很累，所以她自己已经无法回答这个问题了，向你求助……

更正式地说，一条围巾可以表示为一张大小为 n × m 的表格，其中每个单元格的颜色为 k 种颜色中的一种。颜色从 1 到 k 编号。

表格第一行的颜色为 1, 2, ..., k, 1, 2, ..., k 等。下一行是通过移至左侧一个单元格从前一行获得的。因此，桌子由对角条纹组成。

对于n = 4，m = 8表格k = 3将如下所示： 在此输入图像描述 使用给定的数字 n、m、k 和 c，确定总共有多少个单元格被着色为 c。

输入 输入的第一行包含一个自然数 n - 围巾的宽度。

输入的第二行包含一个自然数m——围巾的长度。

输入的第三行包含自然数 k — Alice 的朋友最喜欢的颜色的数量。

数量n不超过。m_k109

输入数据的第四行包含自然数c——特殊颜色的数量(1 ≤ c ≤ k)。

输出 程序应输出一个整数 - 颜色为 c 的围巾单元的数量。

注意： 请注意，本题的答案可能超出 32 位整型变量的可能值，因此必须使用 64 位整型数据类型（Pascal 中为 int64，C++ 中为 long long，Java 和 C# 中为 long）。

评分系统

当 n 小于 10 时正确工作的解决方案将获得 16 分。

当数字 n 或 m 之一能被 k 整除时，正确工作的解将值 16 分。

当 n 和 m 小于 800 时正确工作的解决方案将值 40 分。

当 n 和 m 小于 105 时正确工作的解决方案将获得 60 分。

评论

该图片对应于条件中的示例。围巾尺寸为 4 × 8，由三种颜色的格子组成。11 个单元格涂成颜色 1。

输入数据：

4
8
3
1

输出：

11

这是我的代码：

n = int(input())
m = int(input())
k = int(input())
c = int(input())

color_counts = [0] * k

# Левая часть диагоналей
left_diagonals = n - k
left_diagonal_length = k - 1
color_counts[c-1] += left_diagonals * left_diagonal_length

# Средняя часть диагоналей
middle_diagonals = n // k
middle_diagonal_length = k
color_counts[c-1] += middle_diagonals * middle_diagonal_length

# Правая часть диагоналей
right_diagonals = n - k
right_diagonal_length = n % k
color_counts[c-1] += right_diagonals * right_diagonal_length

result = color_counts[c-1] * m

print(result)
python

1 个回答

  1. Best Answer

    给定的代码是二次的，它可能给出正确的答案，但它不会及时通过。

    让我们看一个矩阵，例如数字 2。

    数字c位于对角线上。对角线的左侧部分是不完整的，它们被左边缘切断，它们的长度较小。n
    然后是对角线的中间部分 - 它们从上到下，它们的长度。n
    然后是右侧部分 - 对角线开始从右边缘到底部，它们也是不完整的

    剩下的就是求出所有部分对角线的条数以及左右部分的长度范围（长度是等差数列，所以求和并不难，主要是找出这些进展）

    运行时间是常数 O(1)

    def countc(n, m, k, c):
    n, m = min(n, m), max(n, m)  #ввиду симметрии задачи обеспечим m>=n
    cnt = 0

    #номер последней c-содержащей левой диагонали
    numld = max(0, 1 + (n - 1 - c) // k)  
    cnt += (2*c + (numld-1)*k) * numld // 2

    #номер последней c-содержащей средней (полной длины) диагонали 
    md = (m - 1 - c) // k
    cnt += n*(md-numld+1)

    r1 = md + 1
    #номер последней c-содержащей правой диагонали
    r2 = (n + m - 1 - c) // k
    rd = max(0, r2 - r1 + 1)
    len1 = n - (c + r1*k - m)
    len2 = n - (c + r2*k - m)
    cnt += rd*(len1+len2)//2

    return cnt
    • 2

相关问题