Binary codes   poj1147
Time Limit:1000MS Memory Limit:65536K
Total Submit:1695 Accepted:626

Description

Consider a binary string (b1…bN) with N binary digits. Given such a string, the matrix of Figure 1 is formed from the rotated versions of the string.

  b1   b2 … bN-1 bN

  b2   b3 … bN   b1

  …

  bN-1 bN … bN-3 bN-2

  bN   b1 … bN-2 bN-1



  Figure 1. The rotated matrix

Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’. You are to write a program which, given the last column of the sorted matrix, finds the first row of the sorted matrix.

As an example, consider the string (00110). The sorted matrix is

  0 0 0 1 1

  0 0 1 1 0

  0 1 1 0 0

  1 0 0 0 1

  1 1 0 0 0

and the corresponding last column is (1 0 0 1 0). Given this last column your program should determine the first row, which is (0 0 0 1 1).

Input

The first line contains one integer N ≤ 3000, the number of binary digits in the binary string. The second line contains N integers, the binary digits in the last column from top to bottom.

Output

The first line contains N integers: the binary digits in the first row from left to right.

Sample Input

5
1 0 0 1 0

Sample Output

0 0 0 1 1

Source
IOI 2001 (back-up task)


[ 此贴被kangtalc在2007-04-16 12:28重新编辑 ]

AC的代码哈，记得加浮云，都穷死了。

Copy code

#include <iostream>
using namespace std;
#define N 3005
int main()
{
   int num,a[N];
   int next[N];
   int b[N];
   cin>>num;
   int i;
   int cnt=0;
   for(i=0;i<num;i++)
   {cin>>a[i];
   cnt+=a[i];
   }
   for(i=0;i<num-cnt;i++)
       b[i]=0;
   for(i=num-cnt;i<num;i++)
       b[i]=1;
   int j=0;
   for(i=0;i<num;i++)
       if(a[i]==0)
           next[j++]=i;
       j=num-cnt;
       for(i=0;i<num;i++)
           if(a[i]==1)
               next[j++]=i;
           i=0;
           
           while(num--)
           { cout<<a[next[i]]<<" ";
           i=next[i];
           }
           cout<<endl;
           
           
           return 0;
}

Quote:

引用第25楼hygel于2007-04-15 14:29发表的:
此处是被引用的隐藏贴

想法太天真了哈，仔细思考下