暑假集训(1)第一弹 -----士兵队列训练问题（Hdu1276)

Description

某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

 

Input

本题有多个测试数据组，第一行为组数N，接着为N行新兵人数，新兵人数不超过5000。

 

Output

共有N行，分别对应输入的新兵人数，每行输出剩下的新兵最初的编号，编号之间有一个空格。

 

Sample Input

2 20 40

 

Sample Output

1 7 19 1 19 37

 

问题分析 ：

显然最初士兵之间的间隔为1、1......，但是在报二后，只留下奇数位，从而导致他们的间隔会翻倍变为2、2.....，

1  2  3  4  5  6  7.....

1      3      5     7......

而在报三后每三个数失去一位，则间隔变为2、4......

1  3  5  7  9  11  13.......

1  3      7  9       13.......

 

由此假设报二的次数为n次，报三的次数为n次(n!=0)

得士兵排序为1   1+2*3E(n-1)   1+2*3En;  

 

注意：N<=3 和 排列序号大于士兵人数N的情况 以及报二报三次数不一致的情况。

 

#include "iostream"

using namespace std;

int main()
{
    int t,N;
    int i,j,k;
    cin>>t;
    while (t--)
    {
      i=1;
      j=1;
      cin>>N;
      k=N;
      if (N<=3)
      {
        for (int i=1;i<=N;i++)
          {
           cout<<i;
           if (i!=N)
             cout<<' ';
           else
             cout<<endl;
          }
           continue;
      }
      while (1)
      {
          N = N-N/2;
          i = i+j; j = i;
          if (N <= 3)
                 break;
          N = N-N/3;
           j = i+j;
           if (N <= 3)
                 break;
      }
      cout<<1<<' '<<i+1;
      if (i+j+1<=k)
       cout<<' '<<i+j+1;
       cout<<endl;
    }
     return 0;
}