284 - Logic

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

Moderator: Board moderators

Post Reply
itsme86
New poster
Posts: 3
Joined: Tue Sep 14, 2004 9:16 am

284 - Logic

Post by itsme86 » Fri Sep 17, 2004 7:19 am

The judge doesn't want to judge problem 284 because it's not in the database or something. I spent a couple of hours on this code and I don't want it to go to waste so here it is ;)

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
  int x;
  int y;
} COORD;

typedef struct
{
  char ch;
  int inputs_needed;
  int (*func)();
} GATETYPE;

typedef struct
{
  char inputs[2];
  int ninputs;
  COORD outputs[20];
  int noutputs;
  GATETYPE *gate;
} GATE;

int do_and(GATE *);
int do_or(GATE *);
int do_not(GATE *);
int do_input(GATE *);
int do_output(GATE *);

GATETYPE gatetypes[5] =
{
  { '&', 2, do_and    },
  { '|', 2, do_or     },
  { '!', 1, do_not    },
  { 'i', 1, do_input  },
  { 'o', 1, do_output }
};

#define G_AND    (&gatetypes[0])
#define G_OR     (&gatetypes[1])
#define G_NOT    (&gatetypes[2])
#define G_INPUT  (&gatetypes[3])
#define G_OUTPUT (&gatetypes[4])

GATE gates[100];
int ngates;

GATE *grid[10][10];

int parse_coord(char **str, COORD *coord)
{
  char *p = *str;

  while(*p == ' ')
    p++;

  if((!*p || !*(p+1)) || (*p == '.' && *(p+1) == '.'))
    return 0;

  coord->x = *p-'0';
  coord->y = *(p+1)-'0';
  *str = p+2;

  return 1;
}

void run_it(void)
{
  int x, y, i;
  int nprocessed;
  int val;
  GATE *g, *g2;

  do
  {
    nprocessed = 0;

    for(x = 0;x < 10;++x)
      for(y = 0;y < 10;++y)
      {
        g = grid[x][y];

        if(g && g->gate != G_OUTPUT)
        {
          if(g->ninputs == g->gate->inputs_needed)
          {
            val = g->gate->func(g);
            g->ninputs = 0;
            nprocessed++;

            for(i = 0;i < g->noutputs;++i)
            {
              g2 = grid[g->outputs[i].x][g->outputs[i].y];
              g2->inputs[g2->ninputs++] = val;
            }
          }
        }
      }
  } while(nprocessed);
}

int main(void)
{
  char buf[4096], *p;
  int ncircuits;
  int x, y, ch;
  int i;
  int ntests;
  GATE *g;
  COORD c;

  fgets(buf, sizeof(buf), stdin);
  ncircuits = atoi(buf);

  while(ncircuits--)
  {
    memset(grid, 0, sizeof(GATE *)*10*10);
    memset(gates, 0, sizeof(GATE)*100);
    ngates = 0;

    for(;;)
    {
      fgets(buf, sizeof(buf), stdin);
      if(*buf && buf[strlen(buf)-1] == '\n')
        buf[strlen(buf)-1] = '\0';

      if(!strcmp(buf, "end"))
        break;

      x = buf[0]-'0';
      y = buf[1]-'0';
      ch = buf[2];

      for(i = 0;i < 5;++i)
        if(gatetypes[i].ch == ch)
          break;
      if(i == 5)
        continue;
      gates[ngates].gate = &gatetypes[i];
      grid[x][y] = &gates[ngates++];

      g = grid[x][y];
      p = buf+4;
      while(parse_coord(&p, &c))
        g->outputs[g->noutputs++] = c;
    }

    fgets(buf, sizeof(buf), stdin);
    ntests = atoi(buf);

    while(ntests--)
    {
      fgets(buf, sizeof(buf), stdin);
      if(*buf && buf[strlen(buf)-1] == '\n')
        buf[strlen(buf)-1] = '\0';

        for(p = buf, i = 0;i < ngates;++i)
          if(gates[i].gate == G_INPUT)
          {
            gates[i].inputs[gates[i].ninputs++] = *p-'0';
            p++;
          }

      run_it();

      for(i = 0;i < ngates;++i)
        if(gates[i].gate == G_OUTPUT)
        {
          printf("%d", gates[i].inputs[0]);
          gates[i].ninputs = 0;
        }
      printf("\n");
    }
  }

  return 0;
}

int do_and(GATE *gate)
{
  return gate->inputs[0] && gate->inputs[1];
}

int do_or(GATE *gate)
{
  return gate->inputs[0] || gate->inputs[1];
}

int do_not(GATE *gate)
{
  return !gate->inputs[0];
}

int do_input(GATE *gate)
{
  return gate->inputs[0];
}

// do_output() shouldn't ever get called
int do_output(GATE *gate)
{
  return 0;
}

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Sep 17, 2004 7:39 pm

Your program does not work, anyway. I just created some tricky input, and your program crashed.
Try:
1
00i 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ..
01o ..
02o ..
03o ..
04o ..
05o ..
06o ..
07o ..
08o ..
09o ..
10o ..
11o ..
12o ..
13o ..
14o ..
15o ..
16o ..
17o ..
18o ..
19o ..
20o ..
21o ..
22o ..
23o ..
24o ..
25o ..
26o ..
27o ..
28o ..
29o ..
30o ..
31o ..
32o ..
33o ..
34o ..
35o ..
36o ..
37o ..
38o ..
39o ..
40o ..
41o ..
42o ..
43o ..
44o ..
45o ..
46o ..
47o ..
48o ..
49o ..
50o ..
51o ..
52o ..
53o ..
54o ..
55o ..
56o ..
57o ..
58o ..
59o ..
60o ..
61o ..
62o ..
63o ..
64o ..
65o ..
66o ..
67o ..
68o ..
69o ..
70o ..
71o ..
72o ..
73o ..
74o ..
75o ..
76o ..
77o ..
78o ..
79o ..
80o ..
81o ..
82o ..
83o ..
84o ..
85o ..
86o ..
87o ..
88o ..
89o ..
90o ..
91o ..
92o ..
93o ..
94o ..
95o ..
96o ..
97o ..
98o ..
99o ..
end
2
0
1

and I think it is not forbidden to fed an output to another gate (at least there was nothing said like this in problem description). but you also don't handle this.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jul 11, 2005 3:01 pm

Could you Adrian post more IOs ?
I passed your output and run on judge input without crash :) but I still have got WA, soI need help :)

Best regards
DM

PS. I you wish, I can send you my code
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jul 11, 2005 10:29 pm

Never mind, Adrian ...
I got Accepted :) I removed some strange code from my solution and Accepted them ;)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 284 - Logic

Post by anacharsis » Thu Feb 15, 2018 5:13 am

Once you have all of the basic gates set up properly, the thing to check is to make sure you handle chained outputs.

Input:

Code: Select all

1
12i 22 ..
22! 33 ..
33& 53 ..
16i 33 ..
53o 63 ..
63o ..
end
3
01
11
00
Output:

Code: Select all

11
00
00
If you don't chain outputs properly, you'll wind up with 10 as an answer ot the first one.

Post Reply

Return to “Volume 2 (200-299)”