# オフラインリアルタイムどう書く E21 の問題

どちらも循環状態にならないようにチェックしました。

```gcd(X,Y,G):-X=Y,G=X.
gcd(X,Y,G):-Y>X,Y1 is Y-X,gcd(X,Y1,G).
gcd(X,Y,G):-X>Y,gcd(Y,X,G).

lcm(X,Y,L):-gcd(X,Y,G), L is X*Y//G.

cir(N0,L,C):-foldl(plus,L,0,X),lcm(N0,X,C).   %cyclic

solve(_,_,_,_,_,[],_,L,L):-!.
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
C>0,include(var,Mag,VL),not(VL=[]),nth0(N,Mag,X,Mag1),var(X),!,
((member(H,Hit),delete(Hit,H,Hit1),cir(N0,T1,C1),append(Bul,[N],Bul1),
nth0(N,Mag2,0,Mag1),solve(N0,N,C1,T,T1,Hit1,Mag2,Bul1,R));
(N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),C1 is C-H1,nth0(N,Mag2,0,Mag1),
solve(N0,N1,C1,L,L1,Hit,Mag2,Bul,R))).
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
C>0,include(var,Mag,VL),not(VL=[]),N1 is (N+H1) mod N0,
append(T,[H],L),append(T1,[H1],L1),C1 is C-H1,solve(N0,N1,C1,L,L1,Hit,Mag,Bul,R).

start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).

pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,[],[],Tu,Hit),
length(Tu,N1),numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),cir(N0,Tu1,Cir),length(Mag,N0),
solve(N0,0,Cir,Or,Tu1,Hit,Mag,[],R),disp(N0,R,C),pre(T).

ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).

disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).

maked(_,[],Tu,Hit,Tu1,Hit):-reverse(Tu,Tu1).
maked(N,['['|T],Tu,Hit,R1,R2):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,[H|Tu],[N|Hit],R1,R2).
maked(N,[H|T],Tu,Hit,R1,R2):-N1 is N+1,maked(N1,T,[H|Tu],Hit,R1,R2).

%start.

str("0       3[2]3/6 000100
1       21[3]/6 000100
2       12[3]/6 000100
3       3[2]1/6 000100
4       3[2]3/6 000100
5       1[1]3/6 010000
6       [3]4[4]3/7      1000100
8       [4]41[1]/7      1000010
9       1[1]33[1]/8     01000001
10      [1]12[4][3]/8   10100001
11      2[2][1]12/8     01001000
12      1[2][2][1]34/9  011100000
13      [4]1141[2]/9    100000010
14      [3]33[3][2]2/9  100000110
15      [5]1[3]44[2][3]/10      0100101001
16      3[1][2]23[3][1]/10      0110110000
17      33[5]12[5][2]/10        0000010011
18      13[3]1[4][4][4][1]/11   00101100110
19      [5]3[2]35[1]1[4]/11     10001010001
20      4[1]4[5]342[5]/11       00001010100
21      [5][4]55[2][2][4]33/12  001111100000
22      3[2]415[1][4][4]3/12    010101000100
23      3[2][4][2][4]4[5]4[1]/12        011001110010
24      3555[6]33[6]4[1]/13     0010010000010
25      4[1]32[6]3[3]4[3]4/13   0001100001001
26      2[2]14[3][1][6][4]63/13 0010011001010
27      2[9][9][9]8[2]3[4][8]2[1]8/15   011010100001110
28      [1][2][6]64[1][3]68[3][8]8/15   111001000011010
29      [7][6][5]54[5]8[5]53[8]1/15     010001110010001").
```

```gcd(X,Y,G):-X=Y,G=X.
gcd(X,Y,G):-Y>X,Y1 is Y-X,gcd(X,Y1,G).
gcd(X,Y,G):-X>Y,gcd(Y,X,G).

lcm(X,Y,L):-gcd(X,Y,G), L is X*Y//G.

cir(N0,L,C):-foldl(plus,L,0,X),lcm(N0,X,C).

comb(0,_,[]).                                     %combination
comb(N,[H|T],[H|L]):-N>0,N1 is N-1,comb(N1,T,L).
comb(N,[_|T],L):-N>0,comb(N,T,L).

sol(_,_,_,_,_,[],[]):-!.
sol(N0,N,C,[H|T],[_|T1],Hit,Mag):-
C>0,select(N,Mag,Mag1),member(H,Hit),delete(Hit,H,Hit1),cir(N0,T1,C1),
sol(N0,N,C1,T,T1,Hit1,Mag1).
sol(N0,N,C,[H|T],[H1|T1],Hit,Mag):-
C>0,not(member(N,Mag)),N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),
C1 is C-H1,sol(N0,N1,C1,L,L1,Hit,Mag).

solve(N0,Or,Tu,Hit,Mag):-cir(N0,Tu,C),N1 is N0-1,length(Hit,N),numlist(0,N1,L),comb(N,L,Mag),
sol(N0,0,C,Or,Tu,Hit,Mag).

start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0).

pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,[],[],Tu,Hit),length(Tu,N1),
numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),solve(N0,Or,Tu1,Hit,Mag),disp(N0,Mag,C),pre(T).

ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).

disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).

maked(_,[],Tu,Hit,Tu1,Hit):-reverse(Tu,Tu1).
maked(N,['['|T],Tu,Hit,R1,R2):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,[H|Tu],[N|Hit],R1,R2).
maked(N,[H|T],Tu,Hit,R1,R2):-N1 is N+1,maked(N1,T,[H|Tu],Hit,R1,R2).

%start.
```

2018.2.6 すこし解説します。

solveのNには現在の弾倉の番号、Orには人の番号のリスト、TurにはOrに対応する人特有の弾倉の回転数、
Hitには犠牲者の番号、Magには弾倉のリスト（変数）が入っています。

Magが0で満たされるまでにHitが空になれば成功、でなければ失敗してバックトラックします。

solveのMagには弾の入った弾倉の番号の候補が入っています。

その人が犠牲者ならMagからその番号を削除し、犠牲者でない場合失敗し、次の候補を検証します。

2018.2.9 追加

メンバーが変わるときに履歴をリセットすればよいのでした。

2018.2.10 追加

```solve(_,_,_,_,_,[],_,L,L):-!.
solve(_,N,C,[H|_],_,_,L,_,_):-(member(N:H,C);(include(var,L,L1),L1=[])),!,fail.
solve(N0,N,_,[H|T],[_|T1],Hit,Mag,Bul,R):-
nth0(N,Mag,X),var(X),nth0(N,Mag,0),member(H,Hit),delete(Hit,H,Hit1),
C1=[N:H],append(Bul,[N],Bul1),solve(N0,N,C1,T,T1,Hit1,Mag,Bul1,R).
solve(N0,N,C,[H|T],[H1|T1],Hit,Mag,Bul,R):-
nth0(N,Mag,0),N1 is (N+H1) mod N0,append(T,[H],L),append(T1,[H1],L1),
C1=[N:H|C],solve(N0,N1,C1,L,L1,Hit,Mag,Bul,R).

start:-str(S),split_string(S,"\n,\s","\s",L0),pre(L0),!.

pre([]):-!.
pre([_,B,C|T]):-
concat_atom([H,N],/,B),atom_number(N,N0),atom_chars(H,L),maked(1,L,Tu,Hit),
length(Tu,N1),numlist(1,N1,Or),maplist(atom_number,Tu,Tu1),length(Mag,N0),
solve(N0,0,[],Or,Tu1,Hit,Mag,[],R),disp(N0,R,C),pre(T).

ml(0,_,L,L).
ml(N1,R,L1,Re):-N is N1-1,(member(N,R)->L=[1|L1];L=[0|L1]),ml(N,R,L,Re).

disp(N0,R,C):-
ml(N0,R,[],L),atomics_to_string(L,"",S),(S==C->write("yes ");write(" no ")),writeln(S).

maked(_,[],[],[]):-!.
maked(N,['['|T],[H|Tu],[N|Hit]):-!,T=[H,_|T1],N1 is N+1,maked(N1,T1,Tu,Hit).
maked(N,[H|T],[H|Tu],Hit):-N1 is N+1,maked(N1,T,Tu,Hit).
```