2076. The Drunk Jailer

Problem

A certain * contains a long hall of n cells, each right next to each other. Each cell has a *er in it, and each cell is locked.

One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey, and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the hall locking every other cell (cells 2, 4, 6, ...). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ...). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He repeats this for n rounds, takes a final drink, and passes out.

Some number of *ers, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.

Given the number of cells, determine how many *ers escape jail.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

Output

For each line, you must print out the number of *ers that escape when the * has n cells.

Sample Input

2
5
100

Sample Output

2
10

Source: Greater New York 2002

脑子比较笨用的是最北的遍历方法。代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int cell[101];//0表示牢房锁闭，1为打开状态
 5 
 6 int main () 
 7 { 
 8     int n;
 9     scanf("%d",&n);
10     
11     int num;
12     int unlockCount;
13 
14     int i,j;
15 
16     while(n--)
17     {
18         unlockCount=0;
19         memset(cell,0,101*sizeof(int));
20 
21         scanf("%d",&num);
22         for(i=1;i<=num;i++)
23         {
24             for(j=i;j<=num;j+=i)
25             {
26                 if(cell[j] == 0)
27                     cell[j]=1;
28                 else
29                     cell[j]=0;
30             }
31         }
32         for(i=1;i<=num;i++)
33             if(cell[i] == 1)
34                 unlockCount++;
35         printf("%d
",unlockCount);
36     }
37     return 0;
38 }

看到网上还有许多其他解法，一并参考下：

1、转载自：http://blog.csdn.net/sinchb/article/details/8075949

    最笨的方法，就是列一个长度为n的数组代表cell是locked还是unlocked，然后按照游戏方法，遍历n次该数组，不断改变数组中的值，这样时间复杂度是O(n*n)。但是经过观察发现，一个cell被开关的次数其实是有规律的，也就是这个cell的编号n的约数的数量；比如4，他的约数有1,2,4，所以编号为4的cell会在游戏的第1,2,4轮被开/关。又如果一个cell被开/关的最终次数为偶数次，则该cell最终也就是关闭的，这个cell里可怜的*er将无法上演《越狱》，只有cell编号的约数数量为奇数的，才有机会逃跑。所以，问题转换为，求一个数1~n中，有多少数有奇数个约数。

 1 #include <stdio.h>
 2 int main()
 3 {
 4     short unsigned cell[101] = {0,1,1,1,2,2},i = 0,j,top,sum = 0;
 5     int N,n;
 6     for(i = 6;i <= 100;i++)
 7     {
 8         sum = 0;
 9         top = i>>1;
10         for(j = 2;j <= top ;j++)
11             !(i % j) ? sum++ :0;
12         cell[i] = cell[i-1] + sum%2;
13     }
14     scanf("%d",&N);
15     while(N--)
16     {
17         scanf("%d",&n);
18         printf("%d
",cell[n]);
19     }
20     return 0;
21 }

2、转载自：http://zhidao.baidu.com/link?url=4SkSUEHqhMhNniqchgFztGMNMemf8zP-UgP_ZTVE4TqAqfIGYF-UM8z4m_wHaoOhJLC-ILQUGk5ofRY2GfNEEK

代码比较简洁

编号为1的门只为1的倍数，所以只执行了一次操作，所以其最后的状态是开，编号为2的门只为1和2的倍数，执行了两次操作，其最后的状态是关，编号为3的门为1和3的倍数，执行了三次操作，其最后的状态为关，编号为4的门为1、2、4的倍数，执行了三次操作，其最后的状态为开......以此类推，如果编号为一个数的平方数，则其执行操作的次数为奇数次，其最后的状态为开。于是只要求出小于这个数的正整数中有几个数是平方数即可。

 1 #include<stdio.h>
 2 #include<math.h>
 3 int main(void){int n, a, on;
 4     scanf("%d",&n);
 5     while(n--){
 6         scanf("%d",&a);
 7         on=(int)sqrt(a);
 8         printf("%d
",on);
 9     }
10     return0;
11 }

2076. The Drunk Jailer

相关推荐