このディレクトリの索引

#  この問題は秋葉拓哉、岩田陽一、北川宣捻共著 「プログラミングコンテストチャレンジブック」2010年9月 株式会社毎日コミュニケーションズ刊
#  のp73より出題させていただきました。
#  
#  プライオリティキューを用いる問題
#  Expedition (POJ2431)
#  
#  トラックで距離Lの道を移動します。はじめトラックにはガソリンPが
#  積まれています。このトラックは距離1走るとガソリンが1消費されます。
#  途中でガソリンが0になってしまうとトラックは停止してしまい、移動に
#  失敗してしまいます。途中にはN個ガソリンスタンドがあります。
#  各ガソリンスタンドiは道のスタート地点Aiの地点にあって、Biだけ
#  ガソリンを補給することができます。トラックの燃料タンクの容量に
#  制限はなく、いくらでもガソリンを補給することができます。
#  Lトラックは移動完了できるでしょうか?
#  またその際、最少で何回のガソリンの補給が必要でしょう?
#  完了できる場合は最小の補給回数を、できない場合は-1を出力してください。
#  
#  !! 制約
#  ・ 1 =< N =< 10000
#  ・ 1 =< L =< 1000000, 1 =< P =< 1000000
#  ・ 1 =< Ai, 1 =< Bi =< 100
#  
#  
#  以下は@Nikoriksこと、紀信邦さんの書いたプログラム。著作権は同氏にあります。
#  
%  On Monday 6th June 2011, @Nikoriks said:
%  
%  #lpjp 以前尾崎さんが見つけたトラックとガソリンの問題
%  ftp://nojiriko.asia/prolog/POJ2431.html http://poj.org/problem?id=2431 をやってみました.(今日も空き時間に泳いだので)
%  いくつか例題を試してみないと合ってるかどうかわかりませんね.
%  q(給油回数,残り距離,燃料量,残りガススタンドのリスト)
%  Qは横型探索のためのq()のリスト.

go:-poj2431(R),display(R),ttynl.

a(4,4).
a(5,2).
a(11,5).
a(15,10).

road(25,10).

init(Q):-
        road(L,P),
        setof(xl(Pos,X),a(Pos,X),X0),
        reverse(X0,Xl),
        write(Xl),nl,
        Q=[q(0,L,P,Xl)].

poj2431(Result):-
        init(Q),
        solve(Q,Result).
poj2431(-1).

solve(Q,Result):-
        pdeq(q(N,A,P,Xl),Q,Q1),
        A =< P,!,
        Result=N.
solve(Q,Result):-
        pdeq(q(N,A,P,Xl),Q,Q1),
        write(q(N,A,P,Xl)),nl,
        proceed(Xl,N,A,P,Q1,Q2),
        solve(Q2,Result).

proceed([xl(Ai,Bi)|Xl], N,A,P,Q1,Q3):-
        P >= A-Ai,!,
        Pi is P-(A-Ai)+Bi, 
        Ni is N+1,
        penq(q(Ni,Ai,Pi,Xl),Q1,Q2),
        proceed(Xl,N,A,P,Q2,Q3).
proceed(_,_,_,_, Q,Q).

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

reverse(L,R):-
        reverse(L,[],R).

reverse([E|X],Y,Z):-!,
reverse(X,[E|Y],Z).
        reverse([],Y,Y).