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重新编辑 ]

是我的了,别跟我抢

我用不来那个POJ,不明白他所谓的提交格式.提交两次都是COMPILING ERROR
谁能指点一下,我 想我写的没错是正解

对不住各位了,再次证明了我的愚蠢...我的是WRONG ANSWER.
我一定回做出来的

对不住各位了,再次证明了我的愚蠢...我的是WRONG ANSWER.呵呵很不好意思的讲,我也知道算法很不严密了,改好了在去试

我整理出来了,谢谢楼主的鼓励.不过我刚提交时一直是TIME LIMIT EXCEED,是我的算法过于复杂然后超过了时间了吗??还是网速慢提交的时间过长导致的??
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 3000
int main()
{
int i;
int n;
int *zzw=(int*)malloc(N*sizeof(int));
int TO_FIND_THEFIRSTROW(int *, int n);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&(*(zzw+i)));
TO_FIND_THEFIRSTROW(zzw,n);
free(zzw);
return 0;
}
int TO_FIND_THEFIRSTROW(int*zzw,int n)
{
int i,j,sum=0,m,k,min=0,l;

for(j=0;j<n;j++)
{
l=(int)pow(2,(double)j);

min=min+*(zzw+n-1-j)*l;
}

for(i=0;i<n;i++)
{
m=*zzw;
for(k=1;k<n;k++)
*(zzw+k-1)=*(zzw+k);
*(zzw+n-1)=m;

for(j=0;j<n;j++)
{
l=(int)pow(2,(double)j);
sum=sum+*(zzw+n-1-j)*l;
}

if(min>sum)min=sum;
sum=0;
}

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
l=(int)pow(2,(double)j);
sum=sum+*(zzw+n-1-j)*l;
}
if(sum==min)
{
for(i=0;i<n;i++)
printf("%d ",*(zzw+i));
}
m=*zzw;
for(k=1;k<n;k++)
*(zzw+k-1)=*(zzw+k);
*(zzw+n-1)=m;
sum=0;
}
}
新的哈
调试了很久才过
寒一个