2014
02-17

# Queens

Everyone knows about the "eight queens problem", but today you will solve a different one.
We are given triangle lattice of side n, as shown in the Figure below. A queen on the lattice can move along a straight line parallel to any of the sides of the triangle. How many queens can be placed on the lattice at most, without any two queens attacking each other?

Each test case contains a single integer N (1<=N<=10^10), indicating the side of the triangle. The input is terminated by a set starting with N = 0. This set should not be processed.

Each test case contains a single integer N (1<=N<=10^10), indicating the side of the triangle. The input is terminated by a set starting with N = 0. This set should not be processed.

1
2
0

1
1

#include <cstdio>
#include <iostream>

using namespace std;

int main()
{
long long n, a, b, ans;

while( cin >> n, n )
{
n--;
a = n/3;
b = n%3;

ans = a*2+1;
if( b == 2 )	ans++;
cout << ans << endl;
}

return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。