## 11205 - The broken pedometer

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
i got WA several times!
can you tel me what's wrong with my code?

Code: Select all

``````var
t, l, i, n, p, j, x, v : integer;
b : boolean;
s : array [1..100] of string;

procedure valid(z : integer);
var
i, j : integer;
a : array [1..100] of string;
b : boolean;
tmp : string;
begin
b := true;
for i := 1 to n do
begin
a[i] := s[i];
a[i][z] := 'A';
end;
for i := 1 to n-1 do
for j := 1 to n-1 do
if a[j] > a[j+1] then
begin
tmp := a[j];
a[j] := a[j+1];
a[j+1] := tmp;
end;
for i := 1 to n-1 do
if a[i] = a[i+1] then
begin
b := false;
break;
end;
if b then
for i := 1 to n do
s[i][z] := 'A';
end;

begin
readln(t);
for l := 1 to t do
begin
readln(p);
readln(n);
for i := 1 to n do
begin
b := true;
s[i] := '';
for j := 1 to p do
begin
read(x);
s[i] := s[i] + char(x+48);
if j > 1 then b := b and (s[j] = s[j-1]);
end;
end;
if (n <> 1) and (not b) then
begin
i := 1;
while (i <= p) and (length(s) <> 1) do
begin
valid(i);
i := i + 1;
end;
v := 0;
for i := 1 to length(s) do
if s[i] <> 'A' then v := v + 1;
writeln(v);
end else writeln(1);
end;
end.``````

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
can any one tell me his algorithm? rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I used Backtrack.
There are some cases which Greedy algorithm doesn't work.

----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Bitmasks works well for this problem. I coded my solution and got accepted in less than 5 mins

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
rio wrote:I used Backtrack.
There are some cases which Greedy algorithm doesn't work.

----
Rio
please give mi some of that test cases

Paolo
New poster
Posts: 1
Joined: Tue Jul 24, 2007 2:37 pm
Isn't the output for:

Code: Select all

``````1
1
1
0
``````
This:

Code: Select all

``````0
``````
?

The problem definition tells that the output must be the minimum number of active LEDs necessary to display the symbol. But since the only possible symbol doesn't light any, no active LEDs are needed to display it.

Could anyone clarify this output and/or have any ideas for tricky test cases? I've tested my algorithm with the inputs from the forum and some cases of mine, but I keep getting WA-slapped on the face =)

cheers!

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
I got Run time error 2 times! Can any one tell me why?

My method is backtracking.

Code: Select all

``Finally Got AC after N days!``

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re:

Paolo wrote:Isn't the output for:

Code: Select all

``````1
1
1
0
``````
This:

Code: Select all

``````0
``````
?

The problem definition tells that the output must be the minimum number of active LEDs necessary to display the symbol. But since the only possible symbol doesn't light any, no active LEDs are needed to display it.

Could anyone clarify this output and/or have any ideas for tricky test cases? I've tested my algorithm with the inputs from the forum and some cases of mine, but I keep getting WA-slapped on the face =)

cheers!
you can get your answer with this page:

http://www.uvatoolkit.com/problemssolve.php

lcy
New poster
Posts: 1
Joined: Mon Aug 16, 2010 3:13 pm

### Re: 11205 - The Broken Pedometer

I dont know how to wirte the backtrace code for this prob.
does anybody can share his/her c++ code with me ?
thanks~

tapan_chugh
New poster
Posts: 5
Joined: Wed Dec 26, 2012 6:46 am

### Re: 11205 - The Broken Pedometer

I am getting a WA.
My algo is to try all the possible permutations. For our answer the bitwise and of all the test cases with the permutation should be distinct

Code: Select all

``````#include<cstdio>
#include<set>
#define isOn(S, j) (S & (1 << j))
#define setBit(S, j) (S |= (1 << j))
using namespace std;

int tcases;
int main()
{
int T;
int P,N;
scanf("%d",&T);
while(T--)
{
set<int> t;
int p,ta;
scanf("%d%d",&P,&N);
for(int i=0;i<N;i++) //Convert the binary input to decimal
{
p=0;
for(int j=0;j<P;j++)
{
scanf("%d",&ta);
p=2*p+ta;
}
tcases[i]=p;
//printf("%d\n",tcases[i]);
}
if(N==1 && tcases==0)
{
printf("0\n");
break;
}
p=0;
setBit(p,P);
//printf("%d\n",p);
for(int i=1;i<=p;i++)
{
bool flag=true;
t.clear();
for(int j=0;j<N;j++)
{
int q=i&tcases[j];
if(t.find(q)==t.end())
t.insert(q);
else
{
flag=false;
break;
}
}
int s=0;
if(flag)
{
for(int j=0;j<P;j++)
{
if(isOn(i,j))
s++;
}
printf("%d",s);
break;
}
}
printf("\n");
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11205 - The Broken Pedometer

it looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!