UVA 11205 - The broken pedometer

 

 

The Problem

A marathon runner uses a pedometer with which he is having problems. In the pedometer the symbols are represented by seven segments (or LEDs):

But the pedometer does not work properly (possibly the sweat affected the batteries) and only some of the LEDs are active. The runner wants to know if all the possible symbols:

can be correctly identified. For example, when the active LEDs are:

numbers 2 and 3 are seen as:

so they cannot be distinguished. But when the active LEDs are:

the numbers are seen as:

and all of them have a different representation.

Because the runner teaches algorithms at University, and he has some hours to think while he is running, he has thought up a programming problem which generalizes the problem of his sweat pedometer. The problem consists of obtaining the minimum number of active LEDs necessary to identify each one of the symbols, given a number P of LEDs, and N symbols to be represented with these LEDs (along with the codification of each symbol).

For example, in the previous sample P = 7 and N = 10. Supposing the LEDs are numbered as:

The codification of the symbols is: "0" = 1 1 1 0 1 1 1; "1" = 0 0 1 0 0 1 0; "2" = 1 0 1 1 1 0 1; "3" = 1 0 1 1 0 1 1; "4" = 0 1 1 1 0 1 0; "5" = 1 1 0 1 0 1 1; "6" = 1 1 0 1 1 1 1; "7" = 1 0 1 0 0 1 1; "8" = 1 1 1 1 1 1 1; "9" = 1 1 1 1 0 1 1. In this case, LEDs 5 and 6 can be suppressed without losing information, so the solution is 5.

The Input

The input file consists of a first line with the number of problems to solve. Each problem consists of a first line with the number of LEDs (P), a second line with the number of symbols (N), and N lines each one with the codification of a symbol. For each symbol, the codification is a succession of 0s and 1s, with a space between them. A 1 means the corresponding LED is part of the codification of the symbol. The maximum value of P is 15 and the maximum value of N is 100. All the symbols have different codifications.

The Output

The output will consist of a line for each problem, with the minimum number of active LEDs necessary to identify all the given symbols.

Sample Input

2
7
10
1 1 1 0 1 1 1
0 0 1 0 0 1 0
1 0 1 1 1 0 1
1 0 1 1 0 1 1
0 1 1 1 0 1 0
1 1 0 1 0 1 1
1 1 0 1 1 1 1
1 0 1 0 0 1 0
1 1 1 1 1 1 1
1 1 1 1 0 1 1
6
10
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
1 1 0 1 0 0
1 0 0 1 0 0
1 1 1 0 0 0
1 1 1 1 0 0
1 0 1 1 0 0
0 1 1 0 0 0

Sample Output

5
4

 

 

 

第一种解法（超时）

 

 

#define RUN
#ifdef RUN

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <cctype> 
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>

using namespace std;

#define MAXN 110
int P;		// Number of LEDs, eg:7 列数
int N;		// Number of symbols, eg:10 行数
char buf[101][16];	// 存储输入序列
char tmp[101][16];	// buf的复制

int myset[16];	// 排列
bool b[2^16+1];

int minOnes;

void printout(){
	for(int i=0; i<N; i++){
		for(int j=0; j<P; j++){
			cout << buf[i][j];
		}
		printf("\n");
	}
}

void printout2(){
	for(int i=0; i<N; i++){
		for(int j=0; j<P; j++){
			cout << tmp[i][j];
		}
		printf("\n");
	}
	cout << "===================" << endl;
}

int cmp(const void *a, const void *b){
	return strcmp((char*)a, (char*)b);
}

void copyBuf(){
	for(int i=0; i<101; i++){
		for(int j=0; j<16; j++){
			tmp[i][j] = buf[i][j];
		}
	}
}

bool isSame(char* a, char* b){
	for(int i=0; i<P; i++){
		if(a[i] != b[i]){
			return false;
		}
	}
	return true;
}


void decide(){
	
	int ones = 0;
	
	for(int col=0; col<P; col++){
		//printf("%d ", myset[i]);
		if(myset[col] == 1){
			ones++;
		}
		//第i列为0，即第i列不被选中，因此可以把tmp中的第i列全部赋值为0
		else{
			//memcpy(tmp, buf, sizeof(buf));
			copyBuf();
			//printout2();

			for(int row=0; row<N; row++){
				tmp[row][col] = '0';
			}

			//先排列一遍
			qsort(tmp, N, sizeof(tmp[0]), cmp);

			//检验是否有重复
			for(int i=0; i<N-1; i++){

				if(isSame(tmp[i], tmp[i+1])){
					return;
				}

			}

			if(ones < minOnes){
				minOnes = ones;
			}
		}
	}
	//printf("\n");

}

//产生00..0 到11..1的全部组合，共2^7种组合
void subset(int cur, int n){
	if(cur == n){
		decide();
		return;
	}
	else{
		myset[cur] = 1;
		subset(cur+1, n);
		myset[cur] = 0;
		subset(cur+1, n);
	}
}


int main(){

#ifndef ONLINE_JUDGE
	freopen("11205.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif

	int cnt;
	cin >> cnt;

	memset(b, false, sizeof(b));

	while(cnt--){
		cin >> P >> N;
		for(int j=0; j<N; j++){
			for(int k=0; k<P; k++){
				cin >> buf[j][k];
			}
		}

		minOnes = P;
		//printout();
		subset(0, P);
		printf("%d\n", minOnes);
	}

	
}


#endif

 

第二种解法：

参考思想 http://www.questtosolve.com/browse.php?pid=11205

There are up to 15 different LEDs, so there are 2^15 different ways in which they might be active/broken. We can easily test all 100 * 2^15 possibilities.

Represent each symbol as an integer in binary. So, 1 1 0 1 0 is stored as 26 (or 11 if you start from the left; doesn't matter which way you do it). For i from 1 to 2^p, AND together each symbol with i. Then, check if every symbol is unique under this bitmask. We can't afford to do an O(N^2) comparison, so make a boolean array of 2^p cells, b[], and set b[j] to true if j is some symbol under the bitmask i. If the cell is already set to true, then you don't have a unique representation.

Take the minimum number of LEDs needed across all unique representations, and output it.

 

 有许多点创新：

1 读入时顺便把二进制转为了十进制

2 (1<<P) 等效于 2^P

3 避免O(N^2)的比较，事先建立bool空间来记录已访问的值

4 用位于运算和右移来计算一个十进制转为二进制后，该数含有多少位1

5 相比于第一种解法，无需特别的用subset()方法产生全排列，直接增量遍历就行了

事实证明，多次使用memset,memcpy,strcpy,strcmp等方法均会严重使运行速度降低

 

#define RUN
#ifdef RUN

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <cctype> 
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>

using namespace std;

#define MAXN 110
int P;		// Number of LEDs, eg:7 列数，最大15
int N;		// Number of symbols, eg:10 行数，最大100
int buf[105];	// 存储输入序列，转为了十进制的形式
int tmp[105];	// buf的复制

int myset[16];	// 排列
bool b[(1<<16)];


int minOnes;


void play(){
	// 2^P-1
	int bound = (1 << P) - 1;

	int i, j;

	for(i=0; i<=bound; ++i){
		memset(b, false, sizeof(b));
		for(j=0; j<N; ++j){
			int val = buf[j] & i;
			//cout << "val:" << val << endl;
			if(b[val]){
				break;
			}
			else{
				b[val] = true;
			}
		}

		//cout << "j:" << j << endl;
		if(j == N){
			//cout << "j==N" << endl;
			//计算i的二进制数里含有1的个数
			int ones = 0;
			int bit = i;

			while(bit > 0){
				if(bit & 1){
					++ones;
				}
				bit = bit >> 1;
			}

			//cout << "ones:" << ones << endl;
			if(ones < minOnes){
				minOnes = ones;
			}
		}
	}
}

int main(){

#ifndef ONLINE_JUDGE
	freopen("11205.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif

	int cnt;
	cin >> cnt;

	while(cnt--){
		memset(b, false, sizeof(b));
		memset(buf, 0, sizeof(buf));
		cin >> P >> N;
		for(int i=0; i<N; i++){
			for(int j=0; j<P; j++){
				int input;
				cin >> input;

				//从左至右存储为十进制
				if(input)
					buf[i] += (input << j);
				//cout << input << " ";
			}
			//cout << endl;
			//cout << "---" << buf[i] << endl;
		}

		minOnes = P;

		play();
		
		printf("%d\n", minOnes);
	}

	
}


#endif

 

评论

1 楼 hellobin 2013-03-20  

看精妙的算法真的是一种享受