THE DRUNK JAILER 分类: POJ 2015-06-10 14:50 13人阅读 评论(0) 收藏

THE DRUNK JAILER
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 24918   Accepted: 15632

Description

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
poj的一道水题,就是n个牢房,犯人从第一个牢房开始每次改变牢房的状态,如果是锁的,就打开,没有锁,就锁上;
循环n次,看看能逃出去几个犯人
#include <map>
#include <set>
#include <string>
#include <cctype>
#include <climits>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define INF 0x3f3f3f3f
#define ClearAll(A,T) memset(A,T,sizeof(A)) using namespace std; const int Max=100;
int a[110];
int main()
{ int n,m;
while(~scanf("%d",&n))
{
if(n==0)
{
continue;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&m);
int sum=0;
memset(a,0,sizeof(a));
for(int j=2;j<=m;j++)
{
for(int k=j;k<=m;k+=j)
{
a[k]=a[k]==0?1:0;
}
}
for(int i=1;i<=m;i++)
{
if(!a[i])
sum++;
}
printf("%d\n",sum);
}
}
return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

上一篇:北京设计模式学习组bjdp.org第7次活动(2013.08.04)回顾会纪要


下一篇:bzoj 1816: [Cqoi2010]扑克牌