Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

tle

Posted by javaman at 2005-01-20 00:48:15 on Problem 2055
#include <iostream>
#include <cstdio>
#define INF 2000000000
using namespace std;

bool yes;
int mod[21][21],r[21],tr[21],p,best;

void solve(int num,int now) {
int t,i,ii,j;

	if (num>=best) return;
	if (now==0) {
		best=num;
		return;
	}
	t=mod[now][now-1];
	for (i=0;i<p;++i)
		if ((t*i)%p==r[now]) {
			for (j=1;j<now;++j) {
				tr[j]=r[j];
				r[j]=(r[j]-i*mod[j][now-1]%p+p)%p;
			}
			ii=(i==0)?0:1;
			solve(num+ii,now-1);
			for (j=1;j<now;++j)
				r[j]=tr[j];
		
		}

			





int main() {
int n,t1,t2,i,j,k;
	while (true) {
		scanf("%d%d",&n,&p);
		if (!(p+n)) break;
		for (i=1;i<=n;++i) {
			scanf("%d",&r[i]);
			--r[i];
		}
		memset(mod,0,sizeof(mod));
		for (i=1;i<=n;++i) {
			scanf("%d",&j);
			for (;j>0;--j) {
				scanf("%d%d",&t1,&t2);
				mod[i][t1-1]=t2;
			}
			for (j=1;j<i;++j) {
				if (mod[i][j-1]==0) continue;
				t1=mod[j][j-1];
				t2=mod[i][j-1];
				r[i]=((r[i]*t1)%p-(r[j]*t2)%p+p)%p;
				for (k=j;k<n;++k) 
					mod[i][k]=((mod[i][k]*t1)%p-(mod[j][k]*t2)%p+p)%p;
			}
		}
		best=INF;
	/*	for (i=1;i<=n;++i) {
			for (j=0;j<i-1;++j)
				printf("    0");
			for (j=i-1;j<n;++j)
				printf("%5d",mod[i][j]);
			printf(" =%5d\n",r[i]);
		}*/
	
		solve(0,n);
		/*for (i=n;i>=1;--i) {
			t1=mod[i][i-1];
			for (j=0;j<p;++j)
				if ((t1*j)%p==r[i]) break;
			if (j==p) break;
			if ((r[i]=j)>0) ++num;
			for (j=1;j<i;++j)
				r[j]=(r[j]-r[i]*mod[j][i-1]%p+p)%p;
		}*/
		if (best==INF) printf("No solution\n");
		else printf("%d\n",best);
	}
	return 0;
}




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator