Page 2 of 2
Posted: Sat Jun 16, 2007 8:19 am
by hamedv
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]) <> 1) do
begin
valid(i);
i := i + 1;
end;
v := 0;
for i := 1 to length(s[1]) do
if s[1][i] <> 'A' then v := v + 1;
writeln(v);
end else writeln(1);
end;
end.
Posted: Wed Jun 20, 2007 11:27 am
by hamedv
can any one tell me his algorithm?
Posted: Wed Jun 20, 2007 8:03 pm
by rio
I used Backtrack.
There are some cases which Greedy algorithm doesn't work.
----
Rio
Posted: Thu Jun 21, 2007 9:59 am
by sclo
Bitmasks works well for this problem. I coded my solution and got accepted in less than 5 mins
Posted: Wed Jul 04, 2007 7:25 pm
by hamedv
rio wrote:I used Backtrack.
There are some cases which Greedy algorithm doesn't work.
----
Rio
please give mi some of that test cases
Posted: Tue Jul 24, 2007 2:49 pm
by Paolo
Isn't the output for:
This:
?
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!
Posted: Fri Jan 04, 2008 1:56 pm
by hamedv
I got Run time error 2 times! Can any one tell me why?
My method is backtracking.
Re:
Posted: Thu Jul 31, 2008 1:54 am
by x140l31
Paolo wrote:Isn't the output for:
This:
?
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
Re: 11205 - The Broken Pedometer
Posted: Thu Aug 19, 2010 12:21 pm
by lcy
I dont know how to wirte the backtrace code for this prob.
does anybody can share his/her c++ code with me ?
thanks~
Re: 11205 - The Broken Pedometer
Posted: Thu Jan 17, 2013 12:10 pm
by tapan_chugh
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[120];
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]==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");
}
}
Re: 11205 - The Broken Pedometer
Posted: Thu Jan 17, 2013 8:37 pm
by brianfry713
it looks like you figured it out.