このディレクトリの索引
#  以下は@Nikoriksこと、紀信邦さんの書いたプログラム。
#  著作権は Apache License 2.0 
#  
#  On Thursday 2nd June 2011, @Nikoriks said:
#  Face The Right Way (POJ No.3276)
#  
#  N頭の牛が一列に並んでいます。各牛は前か後ろのいずれかを向いています。
#  農夫ジョンはすべての牛を前向きにするために、自動回転機を購入することに
#  しました。
#  この機械は購入時に数Kを設定する必要があり、1回の操作でちょうどK頭の
#  連続する牛の向きを反転させることができます。すべての牛を前向きにする
#  ために、必要な最少の操作回数Mとそれを達成する最小Kを求めなさい。
#  
%  #lpjp 牛の問題を直しました.0〜K-1個のbを左端に付け加えています.
%  こうすることで,機械が左端をはみ出して動くことができるようになります.
%  (Tabの表示はなんとかならないのかな)

% poj3276


go:-
        run3276([b,b,f,b,f,b,b]).

run3276(L):-
        length(L,K),
        generate(K,L,Q),
        solve(Q,Result),
        write(Result),nl.

solve([P|Q],Result):-
        finish(P,Result),!.
solve([P|Q],Result):-
        doit(P,P1),
% write(P1),nl,
        penq(P1,Q,Q1),
        solve(Q1,Result).
finish(N-K-L,(N,K)):-skip(f,L,[]).

doit(N-K-L,P):-
        skip(f,L,L1),
        machine(K,L1,L2),
        N1 is N+1,
        P=N1-K-L2.

skip(D,[D|L],L1):-!,skip(L,L1). 
skip(_,L,L).

generate(0,L,[]):-!.
generate(K,L,Q):-
        add2left(K,K,L,Q1,Q),
        K1 is K-1,
        generate(K1,L,Q1).

add2left(0,K,L,Q1,[0-K-L|Q1]):-!.
add2left(N,K,L,Q1,[0-K-L1|Q]):-
        N1 is N-1,
        addb(N1,L,L1),
        add2left(N1,K,L,Q1,Q).
addb(0,L,L):-!.
addb(N,L,[b|L1]):-
        N1 is N-1,
        addb(N1,L,L1).

machine(0,L,L):-!.
machine(_,[],[]):-!.
machine(K,[C|L],[C1|L1]):-
        turn(C,C1),
        K1 is K-1,
        machine(K1,L,L1).
        turn(b,f):-!.
        turn(f,b).

penq(X,[Y|L],R):-
        X @=< Y,!,R=[X,Y|L].
penq(X,[Y|L],[Y|R]):-!,
penq(X,L,R).
penq(X,[],[X]).