Фальшивая монета
http://acm.pku.edu.cn/JudgeOnline/problem?id=1029
Банк "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); } }