2013
11-09

# THE DRUNK JAILER

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner 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 prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.

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

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.

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

2
5
100

2
10

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
*poj1218
* @author NC
*/
public class Main {

public static void main(String[] args) {
Scanner scan = new Scanner(new BufferedInputStream(System.in));
if (scan.hasNext()) {
int t = scan.nextInt();
for (int i = 0; i < t; i++) {
int n = scan.nextInt();
boolean[] cells = new boolean[n + 1];
for (int j = 1; j < cells.length; j++) {
cells[j] = false;
}
for (int j = 2; j <= n; j++) {
for (int k = j; k <= n; k = k + j) {
if (cells[k]) {
cells[k] = false;
} else {
cells[k] = true;
}
}
}
int count = 0;
for (int k = 1; k <= n; k++) {
if (!cells[k]) {
count++;
}
}
System.out.println(count);
}
}
}
}

方法二:
来自:http://hi.baidu.com/maxupeng/blog/item/39ed10cb390c5df053664f78.html

这题其实是求完全平方数个数的问题。设有n个门，有一数k < = n，若k有x个约数，则遍历的过程中必然对k操作x次。第k个门一开始是关的，若x为偶数，最后依然是关的，若x为奇数，最后一定是开的。
问题变成求约数是奇数的门的个数。对于数N，若该数有约数B，则N/B也必定为该数的约数。当B==N/B时，N的约数为奇数个，N=B*B，即N为完全平方数。
问题转化成求N以内完全平方数的个数。将1..N尽可能地放入一个平方网格中，则对角线上的数必定为完全平方数，网格的最大下标就是N以为完全平方数的个数。即对N开方取整。

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
for (int i = 0; i < n; i++) {
System.out.println((int)Math.sqrt((double)cin.nextInt()));
}
}
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}