Problem 1098 - 城镇距离
Time Limit: 1000MS
Memory Limit: 65536KB
Difficulty:
Total Submit: 87 Accepted: 13 Special Judge: No
Total Submit: 87 Accepted: 13 Special Judge: No
Description
有N个城镇在一条直线上，并且没有任意两个城镇重叠，他们两两的距离有N*(N-1)/2个，
现在按照这些距离的降序告诉你这N*(N-1)/2个距离，让你求出从左到右他们每两个相邻城镇之间的距离
Input
多组数据
每组数据的第一行为N(N<=20) 代表N个城镇
接下来的若干行有N*(N-1)/2个从大到小排列的数字，降序告诉你这N*(N-1)/2个距离，注意这些数都为小于等于400的正整数
当N=0时结束输入
每组数据的第一行为N(N<=20) 代表N个城镇
接下来的若干行有N*(N-1)/2个从大到小排列的数字，降序告诉你这N*(N-1)/2个距离，注意这些数都为小于等于400的正整数
当N=0时结束输入
Output
对于每组输入，按照字典序输出所有可能的排列情况。每组数据输完后以5个 - 结尾
Sample Input
1
2
2
3
5 3 2
0
2
2
3
5 3 2
0
Sample Output
-----
2
-----
2 3
3 2
-----
2
-----
2 3
3 2
-----
Hint
Source
wudired
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int N,d,l[410],x[410],y[410],v[410],o[410],z[410];
void find(int i)
{
if(i>=d){
int j,flag=0,flag2=0;
z[0]=0;
for(j=1;j<=x[0];j++)if(z[++z[0]]!=x[j])
{if(!flag2)flag2=x[j]>z[z[0]]?1:-1;if(flag2<0)break;z[z[0]]=x[j];flag++;}
for(j=y[0];j>=1;j--)if(z[++z[0]]!=y[j])
{if(!flag2)flag2=y[j]>z[z[0]]?1:-1;if(flag2<0)break;z[z[0]]=y[j];flag++;}
if(flag&&flag2>0)
{
for(j=1;j<z[0];j++)printf("%s%d",j-1?" ":"",z[j+1]-z[j]);
printf("\n");
}
return;
}
if(!v[l[i]]){find(i+1);return;}
v[l[i]]--;
int t,j;
t=y[1]-l[i];
if(!o[t]&&t>x[x[0]]&&t<y[y[0]])
{
int flag=1;
for(j=1;flag&&j<=x[0];j++)if(!v[t-x[j]])flag=0;
for(j=2;flag&&j<=y[0];j++)if(!v[y[j]-t])flag=0;
if(flag)
{
for(j=1;j<=x[0];j++)v[t-x[j]]--;
for(j=2;j<=y[0];j++)v[y[j]-t]--;
{o[t]=1;x[++x[0]]=t;find(i);x[0]--;o[t]=0;}
for(j=2;j<=y[0];j++)v[y[j]-t]++;
for(j=1;j<=x[0];j++)v[t-x[j]]++;
}
}
t=x[1]+l[i];
//if(t==y[1]-l[i])return;
if(!o[t]&&t>x[x[0]]&&t<y[y[0]])
{
int flag=1;
for(j=2;flag&&j<=x[0];j++)if(!v[t-x[j]])flag=0;
for(j=1;flag&&j<=y[0];j++)if(!v[y[j]-t])flag=0;
if(flag)
{
for(j=2;j<=x[0];j++)v[t-x[j]]--;
for(j=1;j<=y[0];j++)v[y[j]-t]--;
{o[t]=1;y[++y[0]]=t;find(i);y[0]--;o[t]=0;}
for(j=1;j<=y[0];j++)v[y[j]-t]++;
for(j=2;j<=x[0];j++)v[t-x[j]]++;
}
}
v[l[i]]++;
}
int
main ( int argc, char *argv[] )
{
int i;
while(scanf("%d",&N)!=EOF)
{
if(!N)break;
d=N*(N-1)/2;
memset(v,0,sizeof(v));
memset(o,0,sizeof(o));
for(i=0;i<d;i++)
{
scanf("%d",&l[i]);
v[l[i]]++;
}
x[0]=1;x[1]=0;
y[0]=1;y[1]=l[0];
v[l[0]]--;
z[1]=-1;
find(1);
printf("-----\n");
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int a,b,c,d,e,f;
int dis[405];
int zb[30];
int head,tail;
int n;
int sum,zuida;
int zd,zx,num;
int arr[1000][30];
int moni[30];
int judge(int i)
{
int a,c;
int vis[405];
for (a=zx;a<=zd;a++) vis[a]=dis[a];
//cout<<"FUCK"<<endl;
//for (a=zx;a<=zd;a++) if (dis[a]!=0) cout<<a<<' '<<dis[a]<<endl;
for (a=1;a<=head;a++)
{
c=i-zb[a];
if (vis[c]>0) vis[c]--; else return 0;
}
for (a=tail;a<=n;a++)
{
c=zb[a]-i;
if (vis[c]>0) vis[c]--; else return 0;
}
//for (a=zx;a<=zd;a++) if (dis[a]!=0) cout<<a<<' '<<dis[a]<<endl;
//cout<<"FUCK"<<endl;
return 1;
}
int fuck(int i)
{
int a,c;
for (a=1;a<=head;a++)
{
c=i-zb[a];
dis[c]--;
}
for (a=tail;a<=n;a++)
{
c=zb[a]-i;
dis[c]--;
}
return 1;
}
int pan(int i,int j)
{
int a;
for (a=2;a<=n;a++)
{
int b=arr[i][a]-arr[i][a-1];
int c=arr[j][a]-arr[j][a-1];
if (b>c) return 1;
if (b<c) return 0;
}
return 0;
}
int dfs(int i)
{
int a,b;
//cout<<i<<endl;
//for (a=zx;a<=zd;a++) if (dis[a]!=0) cout<<a<<' '<<dis[a]<<endl;
if (sum==n)
{
for (a=1;a<n;a++) if (zb[a+1]-zb[a]==0) return 0;
for (a=1;a<=num;a++)
{
for (b=1;b<n;b++)
{
if (arr[a][b+1]-arr[a][b]!=zb[b+1]-zb[b]) break;
}
if (b==n) return 0;
}
num++;
for (a=1;a<=n;a++) arr[num][a]=zb[a];
//for (a=1;a<n-1;a++) cout<<zb[a+1]-zb[a]<<' ';
//cout<<zb[n]-zb[n-1]<<endl;
return 0;
}
if (i<=0) return 0;
if (dis[i]==0)
{
int j=i;
while (dis[j]==0 && j>0) j--;
dfs(j);
return 0;
}
//从左
int temp=zb[1]+i;
int vis[405];
for (a=zx;a<=zd;a++) vis[a]=dis[a];
/*
cout<<i<<' '<<temp<<endl;
for (a=1;a<=n;a++) cout<<zb[a]<<' ';
cout<<endl;
for (a=zx;a<=zd;a++) if (dis[a]!=0) cout<<a<<' '<<dis[a]<<endl;
cout<<endl;
*/
if (judge(temp)==1)
{
fuck(temp);
tail--;
zb[tail]=temp;
sum++;
dfs(i);
zb[tail]=0;
sum--;
tail++;
for (a=zx;a<=zd;a++) dis[a]=vis[a];
}
//从右
temp=zb[n]-i;
/*
cout<<i<<' '<<temp<<endl;
for (a=1;a<=n;a++) cout<<zb[a]<<' ';
cout<<endl;
for (a=zx;a<=zd;a++) if (dis[a]!=0) cout<<a<<' '<<dis[a]<<endl;
cout<<endl;
*/
if (judge(temp)==1)
{
fuck(temp);
head++;
zb[head]=temp;
sum++;
dfs(i);
zb[head]=0;
sum--;
head--;
for (a=zx;a<=zd;a++) dis[a]=vis[a];
}
return 0;
}
int main()
{
cin>>n;
while (n!=0)
{
if (n==1) {cout<<"-----"<<endl; cin>>n; continue;}
if (n==2) {cin>>b; cout<<b<<endl; cout<<"-----"<<endl; cin>>n; continue;}
num=0;
zd=0; zx=101010;
zuida=(n-1)*n/2;
memset(dis,0,sizeof(dis));
memset(zb,0,sizeof(zb));
for (a=1;a<=zuida;a++)
{
cin>>b;
dis[b]++;
if (b>zd) zd=b;
if (b<zx) zx=b;
}
/*
for (a=1;a<=n;a++) cin>>moni[a];
for (a=1;a<n;a++)
for (b=a+1;b<=n;b++)
{
zx=min(zx,moni[b]-moni[a]);
zd=max(zd,moni[b]-moni[a]);
dis[moni[b]-moni[a]]++;
}
*/
head=1; tail=n;
zb[head]=1;
zb[tail]=1+zd;
dis[zd]--;
sum=2;
dfs(zd);
for (a=1;a<num;a++)
for (b=a+1;b<=num;b++)
{
if (pan(a,b)==1)
{
for (c=1;c<=n;c++)
{
int temp=arr[a][c];
arr[a][c]=arr[b][c];
arr[b][c]=temp;
}
}
}
for (a=1;a<=num;a++)
{
for (b=2;b<=n;b++)
{
if (b!=n) cout<<arr[a][b]-arr[a][b-1]<<' ';
else cout<<arr[a][b]-arr[a][b-1]<<endl;
}
}
cout<<"-----"<<endl;
cin>>n;
}
return 0;
}
