北航acm试题

Coconuts, Revisited 时间限制:1000 ms 内存限制:65536 KB 总提交:51 (19 users) 正确提交:16 (16 users) 描述 这个故事的题目叫做“椰子（Coconuts）”。 讲述的是在一次海难中五个人和一只猴子被困在了一个孤岛上。他们依靠采拾岛上的椰子度过第一个夜晚。当夜，其中的一个人醒了，他决定取回属于他的那一份椰子。他把椰子分为五份，结果剩下了一个椰子，于是那个人就把自己的那一份藏了起来，并把这个剩下的椰子给那只猴子吃了。 过了一会儿，第二个人起床了，他也做了同样的事情。他把剩下的椰子（有一部分已经被第一个人取走了）分为五份，剩下了一个椰子，他同样把自己那一份藏了起来，把剩下的那个椰子送给那只幸运的猴子吃了。 接着，第三个，第四个，和第五个人又用同样的步骤，做了一样的事情。 第二天早上，大家起床后，大家一起把剩下的椰子平均分为五份，这一次，猴子没有那么幸运——没有椰子再剩下来了。 有一个显而易见的问题，“怎么样计算一开始椰子的总数呢？”，不难发现，其实这个数有无限种可能，比如最小的几个数是3、121等等。但是这都不是我们今天的问题。 我们再回过头来看上面这个问题。现在的问题是，如果我们已经知道了最开始椰子的数量，要使执行上述步骤得以进行的所可能的最多的人数是多少人？ 输入 输入包括一系列整数，每个整数表示一开始采拾的椰子的总数。序列的末尾以一个负数表示输入结束。 输出 对于每一组数据，判断能够参与这个过程的最大的人数是多少。输出的格式参见输出样例。如果无解，也需要输出相应的语句。 样例输入 25 30 3121 -1 13

样例输出 25 coconuts, 3 people and 1 monkey 30 coconuts, no solution 3121 coconuts, 5 people and 1 monkey 14

Doing Windows 时间限制:1000 ms 内存限制:65536 KB 总提交:0 (0 users) 正确提交:0 (0 users) 描述 电脑显示屏幕上屏幕是矩形的。 一个屏幕的宽高比就是它的高度除以宽度。这个性质也适用于那些在屏幕上出现的矩形窗口，就是窗口高度除以它的宽度。对于这个问题，我们假设窗口和桌面的大小规模都是用整数像素来衡量的。 假设你的操作系统只允许窗口按照这个规则改变大小：高度，宽度不能单独改变，只能同时改变且高宽比不能变化。比如，一个窗口是150×100，宽高比是1.5，或者你可以改变成225×150，也是1.5，但是224×150就不可以了。每个窗口可以在桌面上任意移动位置，平移操作，但是必须保证整个窗口在桌面可视，没有超出桌面范围的部分。 给你屏幕的大小和4个窗口的初始化大小（宽高都是整数），请问是否可以通过改变4个窗口的大小（按照如上规则）使得4个窗口恰好可以覆盖整个桌面，且相互之间没有覆盖的部分？ 输入 输入数据包含多组数据，最后以一对0结束。每组数据有5对整数，第一对是屏幕的宽和高，后4对分别是4个窗口的初始化的宽和高。 输出 输出对于每组数据仅一行，包含组数标记(从1开始计数)，然后是Yes或者No，分别表示是否可以达到题目所给的要求。 样例输入 400 400 10 10 35 35 15 15 100 100 200 300 10 10 20 20 30 45 40 60 200 250 10 10 20 20 30 45 40 60 0 0 样例输出 Set 1: Yes Set 2: No Set 3: Yes 15

Semi-prime H-numbers 时间限制:1000 ms 内存限制:65536 KB 总提交:24 (9 users) 正确提交:5 (5 users) 描述 这个问题是来源于David Hilbert的一个练习，他在教学中提出一种叫做4n+1的理论。我们在此对此理论做一些研究。 H数指的是一个正数，它比4的倍数多1。 比如 1，5，9，13，17，21?? 这些都是H数。对于今天我们讨论这个问题，我们的仅限于上面指出的这些数里。在乘法中，这些H数构成了一个“闭”的集合。 像所有整数中一样，我们把H数划分为H素数，和H合数。1是单元元素。如果一个H数h不是单位元素，且把它分解为两个H数的乘积只有1*h一种方式，则说它是H质数。余下的数为H合数。 举例来说，最小的几个H合数是：5×5 = 25，5×9=45，5×13=65，9×9=81，5×17=85。 留给你的任务是统计H半素数的个数。如果一个H数是两个H素数的乘积，则称作H半素数。这两个H素数可以相同也可以不同，上面举例的那五个H数都是H半素数。125不是H半素数，因为125=5*5*5，它是3个H素数的乘积。 输入 输入由许多行组成，每一行包含一个H数h （h≤1,000,001）。最后一行一个0表示输入结束，不需要做处理。 输出 对于每一个输入的H数h，输出一行，包括h，以及1和h之间的H半素数，两个数之间用空格隔开。具体格式参见样例输出。 样例输入 21 85 789

16