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

Post 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.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv »

can any one tell me his algorithm? :cry:

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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:

Post by sclo »

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

Post 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

Paolo
New poster
Posts: 1
Joined: Tue Jul 24, 2007 2:37 pm

Post by Paolo »

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

Post by hamedv »

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:

Post by x140l31 »

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

Post 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~

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

Re: 11205 - The Broken Pedometer

Post 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");
    }
}

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

Re: 11205 - The Broken Pedometer

Post by brianfry713 »

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

Post Reply

Return to “Volume 112 (11200-11299)”