Отримання знань

   Банк "Gold Bar" получил информацию из достоверных источников, что в последней партии из N монет содержится одна фальшивая, которая отличается по весу от остальных монет (другие монеты одного веса). После экономического кризиса банку доступны только простые весы, используя которые можно определить, что вес объектов в левом лотке меньше, равен или больше чем вес объектов в правом лотке. Для того чтобы определить фальшивую монету, работники банка перенумеровали все монеты целыми числами от 1 до N, поставив таким образом в соответствие каждой монете уникальный целый идентификатор. После этого они начали взвешивать различные группы монет, помещая одинаковое количество монет в левом и правом лотках. Идентификаторы монет и результаты взвешиваний были тщательно записаны. Вы должны написать программу, которая поможет работникам банка определить идентификатор фальшивой монеты, используя результаты этих взвешиваний.  

   Входные данные

   В первой строке содержатся два числа N (2 <= N <= 100) и K (1 <= K <= 100), разделённые пробелами, где N - количество монет, а K - количество сделанных взвешиваний. Следующие 2*K строк описывают результаты всех взвешиваний. Каждое взвешивание представляется двумя идущими друг за другом строками. В первой из них содержится число монет Pi, размещённых в каждом лотке, после которого идут идентификаторы монет, сначала Pi идентификаторов монет в левом лотке, потом Pi идентификаторов монет в правом лотке. Все числа разделяются пробелами. Вторая строка содержит один из следующих символов: '<', '>' или '='. Они обозначают результат взвешивания:
   '<' означает, что вес монет в левом лотке меньше веса монет в правом;
   '>' означает, что вес монет в левом лотке больше веса монет в правом;
   '=' означает, что вес монет в левом лотке равен весу монет в правом.

   Выходные данные

   Запишите в выходной файл идентификатор фальшивой монеты или 0, если невозможно её определить по результатам представленных взвешиваний.

   Пример входных данных

5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

   Пример выходных данных

3

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1029;
const  maxn = 1000;

type integer = longint;

var a, b: array[1 .. maxn shr 1] of integer;
    x: array[1 .. maxn, 1 .. 3] of integer;
    n, m: integer;

procedure prepare;
begin
  readln(n, m);
  fillchar(x, sizeof(x), 0);
end;

function main: integer;
var i, j, k, p, q, s, sum: integer;
    ch: char;
begin
  main := 0; sum := 0;
  for j := 1 to m do begin
    read(k);
    for i := 1 to k do read(a[i]);
    for i := 1 to k do read(b[i]);
    readln;
    readln(ch);
    if (ch = '<') then
      for i := 1 to k do begin
        inc(x[a[i], 1]);
        inc(x[b[i], 2]);
      end;
    if (ch = '>') then
      for i := 1 to k do begin
        inc(x[a[i], 2]);
        inc(x[b[i], 1]);
      end;
    if (ch = '=') then
      for i := 1 to k do begin
        inc(x[a[i], 3]);
        inc(x[b[i], 3]);
      end
    else sum := sum + 1;
  end;
  p := 0; q := 0; s := 0;
  for i := 1 to n do if (x[i, 3] = 0) then begin
    if (x[i, 1] = sum) and (x[i, 1] > 0) then
      if p = 0 then p := i else exit;
    if (x[i, 2] = sum) and (x[i, 2] > 0) then
      if q = 0 then q := i else exit;
    if s = 0 then s := i else s := -1;
  end;
  if p * q > 0 then exit;
  if (p + q = 0) and (s > 0) then main := s else
  if p = 0 then main := q else main := p;
end;

begin
  prepare;
  writeln(main);
end.

    Пример решения на С++:

#include < stdio.h >
#include < vector >
#include < memory >
using namespace std;

bool getout[1001];
bool left[1001];
bool right[1001];
bool all[1001];
int main()
{
 int N,K,Pi;
 char op;
 vector vi;
 while(scanf("%d%d",&N,&K)==2)
 {
 
  memset(getout,0,N+1);
  memset(left,0,N+1);
  memset(right,0,N+1);
  for(int i=0;i
  {
   memset(all,1,N+1);
   scanf("%d",Π);
   vi.clear();
   int num;
   for(int j=0;j<2*Pi;j++){
    scanf("%d",&num);
    all[num]=false;
    vi.push_back(num);
   }
   scanf(" %c",&op);
   if(op=='='){
    for(int j=0;j<2*Pi;j++){
     getout[vi.at(j)]=true;
    }
   }
   else{
    for(int k=1;k<=N;k++){
     if(all[k])
      getout[k]=true;
    }
    if(op=='>'){
     for(int j=0;j
      right[vi.at(j)]=true;
      if(left[vi.at(j)]){
       getout[vi.at(j)]=true;
      }
     }
     for(int j=Pi;j<2*Pi;j++){
      left[vi.at(j)]=true;
      if(right[vi.at(j)]){
       getout[vi.at(j)]=true;
      }
     }
    }
    else if(op=='<'){
     for(int j=Pi;j<2*Pi;j++){
      right[vi.at(j)]=true;
      if(left[vi.at(j)]){
       getout[vi.at(j)]=true;
      }
     }
     for(int j=0;j
      left[vi.at(j)]=true;
      if(right[vi.at(j)]){
       getout[vi.at(j)]=true;
      }
     }
    }
   }
  }
  bool one=false;
  int output=0;
  for(int k=1;k<=N;k++){
   if(!getout[k]){
    if(one){
     output=0;
     break;
    }
    else{
     one=true;
     output=k;
    }
   }
  }
  printf("%d\n",output);
 }
}