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 » Sat Jun 16, 2007 8:19 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]) <> 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 » Wed Jun 20, 2007 11:27 am

can any one tell me his algorithm? :cry:

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

Post by rio » Wed Jun 20, 2007 8:03 pm

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 » Thu Jun 21, 2007 9:59 am

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 » Wed Jul 04, 2007 7:25 pm

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 » Tue Jul 24, 2007 2:49 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

Post by hamedv » Fri Jan 04, 2008 1:56 pm

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 » Thu Jul 31, 2008 1:54 am

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 » Thu Aug 19, 2010 12:21 pm

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 » Thu Jan 17, 2013 12:10 pm

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 » Thu Jan 17, 2013 8:37 pm

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)”