Cod sursa(job #110553)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 26 noiembrie 2007 22:25:12
Problema NKPerm Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

#define VI vector <char>
#define EPS 1e-3
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define pb push_back
#define MASK 31

typedef long long lint;
typedef long double ldouble;

map <lint,long double> H;
int n,k,T,p[256],m;

inline lint f(lint x,int i)
{
	int z,y,j=i*5,aux;
	z=(x>>j)&MASK; z^=z-1; y=x^(z<<j); 
	j-=5;
	z=(x>>j)&MASK; z^=z+1; y=y^(z<<j);
	y=(y>>5)<<5; y|=i-1;
	return y;	
}

ldouble doit(lint x)
{
	ldouble aux=H[x],z;
	if(aux>EPS)
		return aux;
	if(aux<-EPS)
		return 0;
	int i,l=x&MASK,y,j=5;
	for(i=1;i<=k;++i,j+=5)
	{
		z=((x>>j)&MASK)-(i==l);
		if(z<=0) continue;
		aux+=doit(f(x,i))*(double)z;
	}
	if(aux>EPS)
		H[x]=aux;
	else
		H[x]=-1;

	return aux;		
}

int main()
{
	int ii,i,iii,l,j;
	char s[16];
	ldouble nr,aux;
	lint x; 
	freopen("nkperm.in","r",stdin);
	freopen("nkperm.out","w",stdout);
	scanf("%d %d %d",&n,&k,&T);
	m=n*k;

	FOR(i,0,k) H[i]=1;
	doit((n<<(5*k))|31);
	FOR(ii,0,T)
	{
		scanf("%s",s);
		if(s[0]=='B')
		{
			scanf("%Lf",&nr);
			FOR(i,0,n) p[i]=k;
			x=(n<<(5*k))|n;
			l=n;
			FOR(iii,0,m)
			{
				FOR(i,0,n) if(p[i]&&i!=l)
				{
					aux=doit(f(x,p[i]));
					if(aux>nr-EPS)
					{
						l=i;
						x=f(x,p[i]--);
						printf("%d ",i+1);
						break;
					}
					nr-=aux;					
				}
			}
			printf("\n");
		}
		else
		{
			nr=0;
			FOR(i,0,n) p[i]=k;
			x=(n<<(5*k))|n;
			l=n;
			FOR(iii,0,m)
			{
				scanf("%d",&j);
				FOR(i,0,j) if(p[i]&&i!=l)
				{
					aux=doit(f(x,p[i]));
					if(i!=j-1)
						nr+=aux;
					else
						l=i,x=f(x,p[i]--);
				}
			}
			printf("%.0Lf\n",nr+1);
		}
	}
	return 0;
}