Я решил задачу с помощью графа, где вершинки - состояния ёмкостей,и рассмотрел из очередного состояния все переходы, запоминая те состояния ,где уже был.
Но я никак не могу оценить кол-во возможных состояний. Может кто-нибудь подскажет как оценить? Самая грубая оценка - у нас есть числа a,b,c>=0 и a+b+c=N(для случая,когда не подливаем и не выливаем-в этом случае сумма константа). Тогда количество таких чисел O(N^3),но это ужасная оценка.

I was using QUEUE.
It was Memory limit exceed #8 or something similar.
Replaced queue by simple an static array of one million elements.
I was using state struct.
There are three members of unsigned char type.
So,  with C limitations, I got AC with 16 MB.

Obviously USED array is MLE.  Probably using unordered_set is OK. Are there better things than unordered_set?  Maybe there are some mathematical properties?..

DFS, record the state, if come into a state appeared before , ignore it.
DFS is very slow, can anybody give some hints to DP?

who give AC, please, give me right answers for this tests :
1) 1 200 245
2) 0 13 131
3) 37 39 41
4) 29 41 97
5) 0 64 129
6) 81 27 243
7) 240 241 242

thanx

Edited by author 14.08.2008 21:51

0 also answer???

Edited by author 25.02.2006 14:04

I have WA6

Edited by author 18.09.2006 22:29

Edited by author 18.09.2006 22:29

My program always WA in Test#6. What is Test#6?







program Problem;



function min( x, y: integer ): integer;
begin
   if x < y then  result:=x else result:=y;
end;
function max(x, y: integer): integer;
begin
    if x > y then result := x else result := y;
end;
type

   TKan = array[0..2]of byte;
var
   Ok: array[0..255, 0..255, 0..255 ] of Boolean;
   R: array[1..1000] of boolean;
   K, Y: TKan;
   Count: Integer;

procedure Calc(X: TKan );
var
   d, i, j: byte;
begin
    if not Ok[X[0], X[1], X[2]] then
     begin
        Ok[X[0], X[1], X[2]] := true;
        for i := 1 to 7 do
         R[X[0] * (i and 1) + X[1] * ((i shr 1) and 1) + X[2] * ( ( i shr 2 ) and 1)] := true;
        for i := 0 to 2 do
         if X[i] = 0 then
          begin
             X[i] := K[i];
               Calc(X);
             X[i] := 0;
          end;

        for i := 0 to 2 do
         for j := 0 to 2 do
          if i <> j then
           begin
              d := min(K[i] - X[i], X[j]);
              if d = 0 then continue;
              inc(X[i], d);
              dec(X[j], d);

              Calc(X);

              dec(X[i], d);
              inc(X[j], d);
           end;

      end;
end;
var
   a: integer;
begin

    FillChar(R, Sizeof(R),0);
    FillChar(Ok, Sizeof(Ok),0);
    read(K[0], K[1], K[2]);
    Y[0] := 0;
    Y[1] := 0;
    Y[2] := 0;
    Calc(Y);
    Count := 0;

    for  a := 1 to 1000 do
         if R[a] then
          begin
         // writeln(a);
          inc(count);
          end;
     writeln(count);
end.

problem#1437 WA #1
it's impossible;
2 cases: "crash(int div by zero)" or "output limit"
but you server give WA

WHY!?

include <stdio.h>
int main()
{
    int N;
    scanf("%i",&N);
int b;
scanf("%i",&b);
scanf("%i",&b);
    if (N==0) N=b/0; else while (true) printf("123442343234234343423243242344");
    return 0;
}

If i used
readln(a);
readln(b);
readln(c);
I got WA on test #12
if i used
read(a);
read(b);
read(c);
i pass that test
What the?

What is test 2? i get crash, are the values bigger than 255?