喝醉的狱卒

1. 题目描述

在一所监狱里有一条长长的走廊，沿着走廊排列着n个牢房，编号为1到n。每个牢房有一个囚犯，而且牢房的门都是锁着的。 一天晚上，狱卒很无聊，于是他就玩起了一个人的游戏。第一轮，他喝了一口威士忌，然后沿着走廊，将所有牢房的门打开。第二轮，他又喝了一口威士忌，然后又沿着走廊，将所有编号为2的倍数的牢房锁上。第三轮，他再喝一口威士忌，再沿着走廊，视察所有编号为3的倍数的牢房，如果牢房是锁着的，他就把它打开；如果牢房是开着的，他就把它锁上。他如此玩了n轮后，喝下最后一口威士忌，醉倒了。 当他醉倒后，一些犯人发现他们的牢房开着而且狱卒已经无能为力，他们立刻逃跑了。 给出牢房的数目n，请你确认最多有可能有多少犯人逃出了监狱？

输入：

仅一行，为一个正整数n，n<=10000。

输出：

仅一行，一个整数，为最多逃跑的犯人数。

样例输入：

5 样例输出：

2

2. 分析

牢房门的状态会在其因子出现的时候改变（从开到关或从关到开）。因此，一个牢房门最终的状态取决于它的编号有多少个因子。只有完全平方数的牢房门会有奇数个因子（因为完全平方数的因子可以配对，除了平方根之外），这导致它们最终处于打开状态。 由于问题要求的是最终打开状态的门的数量，我们知道这等于完全平方数的数量。因此，我们可以直接计算1到n之间完全平方数的数量，从而得到答案。

3. 代码

import math

def max_escapees_optimized(n):
    # 计算1到n之间完全平方数的数量
    return int(math.sqrt(n))

# 主函数，读取输入并打印输出
if __name__ == "__main__":
    n = int(input())
    print(max_escapees_optimized(n))