Cod sursa(job #51040)

Utilizator slayer4uVictor Popescu slayer4u Data 9 aprilie 2007 19:45:06
Problema NextSeq Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m,p,num,a[10001],b[10001],x[10001],i,j,one[10001],aux;
void add(int a[], int b[])
{
	int i,t=0;
	for (i=1;i<=a[0] || i<=b[0] || t;i++,t/=(n+1))
		a[i]=(t+=a[i]+b[i])%(n+1);
	a[0]=i-1;
}
int compare(int a[], int b[])
{
	if (a[0]!=b[0]) return 1;
	for (int i=a[0];i>=1;i--)
		if (a[i]!=b[i]) return 1;
	return 0;
}
void fine()
{
	for (int i=1;i<=a[0];i++)
		if (a[i]==0) a[i]=1;
}
int cautbin(int st,int dr,int o)
{
	int m=(st+dr)/2;
	if (x[m]==o)
		return m;
	else
	if (x[m]<o)
		cautbin(m+1,dr,o);
	else
		cautbin(st,m,o);
}
int main()
{
	freopen ("nextseq.in","rt",stdin);
	freopen ("nextseq.out","wt",stdout);

	scanf("%d %d %d",&n,&m,&p);

	for (i=1;i<=n;i++)
		scanf("%d",&x[i]);

	for (i=1;i<=m;i++) scanf("%d",&a[i]);
	for (i=1;i<=p;i++) scanf("%d",&b[i]);


	sort(x+1,x+n+1);

	a[0]=m;
	for (i=m;i>=1;i--)
		a[i]=cautbin(1,n,a[i]);

	b[0]=p;
	for (i=p;i>=1;i--)
		b[i]=cautbin(1,n,b[i]);
	for (i=1;i<=p/2;i++)
		aux=b[i],b[i]=b[p-i+1],b[p-i+1]=aux;
	for (i=1;i<=m/2;i++)
		aux=a[i],a[i]=a[m-i+1],a[m-i+1]=aux;

	one[0]=one[1]=1;
	num=0;
	while (compare(b,a)!=0)
	{
		fine();
			num++;
		add(a,one);
	}

	printf("%d\n",num-1);
	return 0;
}