11205 - The broken pedometer
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=2146
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 numberPof LEDs, andNsymbols to be represented with these LEDs (along with the codification of each symbol).
For example, in the previous sampleP= 7 andN= 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), andNlines 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 ofPis 15 and the maximum value ofNis 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
巧用二进制判断两个数在某一种有效LED组(active LEDs)下是否显示是一样的。
都写在注释里了。
完整代码:
/*0.116s*/
#include <cstdio>
#include <cstring>
const int P = 1 << 15, maxn = 105;
bool vis[P + 5];
int a[maxn];
int count(int n)///统计n的二进制中1的个数
{
int sum = 0;
while (n)
{
if (n & 1)
++sum;
n >>= 1;
}
return sum;
}
int main()
{
int t, p, n, x, i, j, ans, up;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &p, &n);
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
for (j = 1; j < p; j++)
{
scanf("%d", &x);
a[i] = (a[i] << 1) + x;///把01串压缩成一个数
}
}
ans = maxn, up = 1 << p;
for (i = 0; i < up; i++)///枚举
{
int bits = count(i);
if (bits >= ans) continue;
memset(vis, 0, sizeof(vis));
for (j = 0; j < n; ++j)
{
int pos = a[j] & i;///a[j]在i下的显示结果
if (vis[pos])///说明有两个数显示是一样的
break;
vis[pos] = true;
}
if (j < n) continue;
ans = bits;
}
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
The Privacy Friendly Pedometer stores the user's step count per hour. The user can review the recorded steps in a daily, weekly and monthly report. These reports also display the calculated distance ...
pedometer-master2
Pedometer 手机计步器
runtastic_Pedometer是一个锻炼身体的软件
Android开源项目pedometer-.zip
React型计步器对iOS 8.0及更高版本的React Native计步器支持。... 用库扩展链接二进制文件。 单击加号按钮,然后在Workspace下添加libRNPedometer.a 。 运行您的项目(⌘+ R)。基本用法// Import the reac
一个简单,轻量的计步器app,使用硬件传感器计算步数,而且对电池的消耗非常小。
Wearable computing devices can range providing very specific, limited features like heart rate monitoring and pedometer capabilities to advanced “smart” functions and features similar to those a ...
该计步器使用内置传感器来计算步数。没有GPS跟踪,因此可以大大节省电池。它还会跟踪您消耗的卡路里,步行距离和时间等。所有这些信息将清楚地显示在图表中。 只需点击开始按钮,它将开始计算您的步数。无论您的...
Pedometer 计步器 源代码 加速度传感器采用ADXL330
pedometer sensor sample
计步器上位机APP,兼容飞思卡尔sensor
Android 开源项目pedometer源码 .rar
一个简单,轻量的计步器app,使用硬件传感器计算步数,而且对电池的消耗非常小。对学习计步功能而言是不错的项目。
Android 开源项目pedometer.zip源码资源下载Android 开源项目pedometer.zip源码资源下载
安卓开发-开源项目pedometer .zip
Pedometer仿微信运动走路步数统计源码
Android程序研发源码开源项目pedometer.zip
Android应用源码之开源项目pedometer .zip