ACM竞赛逃脱难题：醉酒狱警与解锁策略

"ACM竞赛练习题，包含答案" 在ACM竞赛中，参赛者经常会遇到各种类型的算法问题，旨在锻炼编程思维和优化解决方案的能力。本资源提供的是一组ACM竞赛练习题，每道题目都有相应的解答，对于学习者来说是很好的参考资料。其中一道题目为"E. THE DRUNK JAILER"，这是一道关于数学和逻辑推理的问题。 题目描述了一位喝醉的狱警在监狱的长廊里进行游戏。长廊有n个相邻的牢房，每个牢房里都关着一个囚犯，所有的牢房都是锁着的。狱警每轮游戏会按照特定规则解锁或锁定牢房。第一轮他解锁所有牢房；第二轮他锁定所有偶数编号的牢房；第三轮他访问每个第三号的牢房，如果牢房是锁着的则解锁，如果已经解锁则重新上锁。这个过程会持续n轮，然后狱警喝完最后一口威士忌后昏迷不醒。 在这个过程中，一旦某个囚犯发现自己所在的牢房被解锁，并且狱警无法阻止他们，他们就会立即逃跑。任务是计算在狱警昏迷后能成功逃出监狱的囚犯数量。 输入部分，首先是一个正整数，表示接下来的测试用例数量。每个测试用例又是一个介于5到100之间的正整数n，表示牢房的数量。 输出部分需要针对每个测试用例，给出在狱警的游戏结束后，有多少囚犯能够成功逃脱。 解决这个问题的关键在于理解狱警操作的规律，并找到在n轮后哪些牢房会保持解锁状态。由于游戏规则是周期性的，可以利用模运算来确定每一轮结束后牢房的状态。例如，对于一个有偶数个牢房的情况，初始时所有牢房都是锁着的，因此在第一轮结束后所有牢房都会被解锁，然后在第二轮结束时所有偶数编号的牢房会被重新锁定。在第三轮结束后，原本偶数编号的牢房（现在是奇数编号）会被解锁，而原本奇数编号的牢房（现在是偶数编号）仍被锁定。通过观察这种模式，我们可以推断在n轮游戏后，所有初始位置为3的倍数的牢房将处于解锁状态。 这个问题涉及到循环、模运算和状态转移，是ACM竞赛中常见的题型，对于理解和应用数学逻辑非常有益。通过解这类题目，参赛者可以提升对算法的理解和实现能力，提高在实际编程竞赛中的竞争力。