Описание
Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски надписано целое число миллилитров, которое вмещается в часть пробирки от дна до этой риски (рис. 3.2)

Изначально первая пробирка содержит 100 миллилитров пива, а остальные две пусты

Задание
Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр пива, и если да, то находит минимально необходимое для этого число переливаний. Пиво можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски


Входные данные
В первой строке входного файла содержится число рисок N (1
N20), имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания следуют N целых чисел V1,V2,...,VN (1Vi100), приписанных рискам. Последняя риска считается сделанной на верхнем крае пробирок (Vn=100)

Выходные данные
В первой строке выходного файла должна содержаться строка "YES", если в третьей пробирке возможно отделить один миллилитр пива, и "NO" в противном случае. В случае ответа "YES" во вторую строку необходимо вывести искомое количество переливаний


Например:

BOOTLING.IN
4
13 37 71 100

BOOTLING.OUT
YES
8

 



Идеи
Построение перечислителя, поиск в ширину

Комментарии
Рассмотрим более общий случай - для каждой пробирки имеется свой набор рисок, в который мы по соглашению дополнительно включаем риску со значением "0" (а риски со значением 100 в этом решении нам, как раз, совсем не нужны). Таким образом, для исходной задачи мы считаем, что третья пробирка имеет единственную "нулевую" риску

Построим граф, изображающий возможные состояния набора из трех пробирок и возможные переходы между ними. Состояние задается тройкой неотрицательных целых чисел (х1,х2,х3), где хi - количество пива в пробирке i и х1+х2+x3=100 . Опишем теперь перечислитель вершин (х1',х2',х3') графа, в которые можно перейти из вершины (х1,х2,х3) за одно переливание

Рассмотрим, для определенности, случай переливания из пробирки i в пробирку j (1
i,j3). Пусть в результате было перелито Δ миллилитров пива, т.е.

хi' = хi - Δ,  хj' = xj + Δ,  хk' = хk

где k= 6-i-j. Наша задача сейчас - определить список возможных значений для Δ. Для этого обозначим через ri1,ri2,...,ris те значения рисок пробирки i, которые меньше хi, а через rj1,...,rjt - те значения рисок пробирки j, которые меньше хj. Ясно, что тогда

Δ { xi - ri1, ..., xi - ris, rj1 - xj, ..., rjt - xj }

Далее осталось найти кратчайший путь в построенном графе, взяв в качестве начальной вершину (х1,х2,х3), а в качестве конечных - вершины (х1,х2,x3) с x3 =1





Решение

{$A+,B-,D+,E+,F-,G-,I-,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 65520,0,655360}

program bootling;
uses
Dos;
const MaxMoves = 200;
type Ar1 = Array[0..100,0..100] of LongInt;
     Ar2 = Array[1..10000] of record a,b : Byte; End;
var A,B,C,D,E,F,N,S : LongInt;
    Q : Ar1;
    V : Array[1..200] of Byte;
    O,O1 : ^Ar2;
    NO,NO1 : LongInt;
 
Procedure ReadFile;
Begin
  Assign(Input,'bootling.in');
  ReSet(Input);
  ReadLn(N);
  B:=0;
  For A:=1 to N do
    Read(V[A]);
  For A:=1 to N do
    If V[A]=100 then B:=1;
  If B=0 then begin Inc(N); V[N]:=100; End;
  Close(Input);
End;
 
Procedure Rec(Z,X:Byte;M:LongInt);
Var  A:LongInt;
Begin
  If Q[Z,X]<>0 then Exit;
  For A:=1 to NO1 do
    If (O^[A].a=Z) and (O^[A].b=X) then Exit;
  Inc(NO1);
  O1^[NO1].a:=Z;
  O1^[NO1].b:=X;
  Q[Z,X]:=M;
End;
 
Procedure Re(Z,X : Byte;M : LongInt);
Var C,A : Byte;
Begin
  C:=100-Z-X;
  If (Z>0) and (X<=100-Z) then Rec(0,X+Z,M+1);
  If (Z>0) and (C<=100-Z) then Rec(0,X,M+1);
  If (X>0) and (Z<=100-X) then Rec(Z+X,0,M+1);
  If (X>0) and (C<=100-X) then Rec(Z,0,M+1);
  If (C>0) and (Z<=100-C) then Rec(Z+C,X,M+1);
  If (C>0) and (X<=100-C) then Rec(Z,X+C,M+1);
  If (X=0) and (Z>0) and (C<100) then Rec(0,0,M+1);
  If (Z=0) and (X>0) and (C<100) then Rec(0,0,M+1);
  For A:=1 to N do
  Begin
    If (Z>=V[A]-X) and (Xthen Rec(Z-(V[A]-X),V[A],M+1);
    If (Z>V[A]) and (X+Z-V[A]<=100) then Rec(V[A],X+Z-V[A],M+1);
    If (X>=V[A]-Z) and (Zthen Rec(V[A],X-(V[A]-Z),M+1);
    If (X>V[A]) and (Z+X-V[A]<=100) then Rec(Z+X-V[A],V[A],M+1);
    If (C>=V[A]-Z) and (Zthen Rec(V[A],X,M+1);
    If (Z>V[A]) and (C+Z-V[A]<=100) then Rec(V[A],X,M+1);
    If (C>=V[A]-X) and (Xthen Rec(Z,V[A],M+1);
    If (X>V[A]) and (C+X-V[A]<=100) then Rec(Z,V[A],M+1);
  End;
End;
 
Procedure Work;
Begin
  FillChar(Q,SizeOf(Q),0);
  New(O);
  New(O1);
  O^[1].a:=100;
  O^[1].b:=0;
  Q[100,0]:=1;
  NO:=1;
  While NO<>0 do
  Begin
    NO1:=0;
    For A:=1 to NO do
      Re(O^[A].a,O^[A].b,Q[O^[A].a,O^[A].b]);
    NO:=NO1;
    O^:=O1^;
  End;
End;
 
Procedure Out;
Var Max : LongInt;
Begin
  Max:=MaxLongInt;
  For A:=0 to 99 do
  Begin
    B:=99-A;
    If (Max>Q[A,B]) and (Q[A,B]<>0) then
      Max:=Q[B,A];
  End;
  If Max=MaxLongInt then WriteLn('NO') else
  Begin
    WriteLn('YES');
    WriteLn(Max-1);
  End;
  Dispose(O);
  Dispose(O1);
End;
 
Begin
  ReadFile;
  Assign(Output,'bootling.out');
  ReWrite(Output);
  Work;
  Out;
  Close(Output);
End.

 


© Особенности национальных задач по информатике