Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define PB push_back
- #define ZERO (1e-10)
- #define INF (1<<29)
- #define CL(A,I) (memset(A,I,sizeof(A)))
- #define DEB printf("DEB!\n");
- #define D(X) cout<<" "<<#X": "<<X<<endl;
- #define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
- typedef long long ll;
- typedef long double ld;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef pair<int,int> ii;
- typedef vector<ii> vii;
- #define IN(n) int n;scanf("%d",&n);
- #define FOR(i, m, n) for (int i(m); i < n; i++)
- #define REP(i, n) FOR(i, 0, n)
- #define F(n) REP(i, n)
- #define FF(n) REP(j, n)
- #define FT(m, n) FOR(k, m, n)
- #define aa first
- #define bb second
- void ga(int N,int *A){F(N)scanf("%d",A+i);}
- #define MX (222)
- int N,M,V,g[MX][MX],C[MX],T[MX],P[MX],cc,S,cn[MX],R,K[MX];
- char s[32];
- int gb(char*s){
- int b(0);
- F(V)b|=(s[i]=='1')<<i;
- return b;
- }
- int pc(char*s){
- int S(0);
- F(V)S+=s[i]!='-';
- return S;
- }
- bool ck(char*s,int b){
- F(V)if(s[i]!='-'&&((b>>i)&1)!=s[i]-'0')return 0;
- return 1;
- }
- bool alr(){F(N)if(!C[i])return 0;return 1;}
- void kill(int I){
- FF(N)if(!cn[j]&&g[I][j])R-=cn[j]=1;
- }
- void sk(){
- CL(K,0);
- FF(N)if(!cn[j])F(M)K[i]+=g[i][j];
- }
- int snd(){
- int S(0);
- CL(cn,S=0),R=N;
- while(R){
- sk();
- int x,k(-INF);
- F(M)if(K[i]>k)x=i,k=K[i];
- ++S,kill(x);
- }
- return S;
- }
- int main(void){
- while(~scanf("%d%d%d",&V,&N,&M)&&V){
- CL(g,0),CL(C,0),CL(cn,S=0),R=N;
- F(N)scanf("%s",s),T[i]=gb(s);
- F(M){
- scanf("%s",s);
- P[i]=pc(s);
- FF(N)C[j]+=g[i][j]=ck(s,T[j]);
- }
- if(!alr()){printf("Test #%d: PIs don't cover all MTs\n",++cc);continue;}
- while(R){
- sk();
- int x,k(-INF),c;
- F(M)if(K[i]>k||(K[i]==k&&P[i]<c))x=i,k=K[i],c=P[i];
- ++S,kill(x);
- }
- S=min(S,snd());
- printf("Test #%d: No of required PIs = %d\n",++cc,S);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement