Problem:

-->

B: 中島、あれやろうぜ！ - Match Peas War -

問題

中島「うぅっ・・・」

磯野「中島，大丈夫か？」

中島「・・・なんだか嫌な夢を見ていた気がするよ」

磯野「どんな夢だい？」

中島「無限に遊ぶ夢」

磯野「意味わからん．まぁいいや，中島，あれやろうぜ！」

中島「あれってまさか，あれじゃないよな・・・」

磯野「あれだよ，あれ」

中島「おっ，いいじゃないか！やろうやろう」

磯野「それじゃあ，まずはじゃんけんだな！」

なにやら，公園で2人の子供が遊んでいるようです．懐かしさを感じますね．ところで，あなたは『マッチ・グリーンピース・戦争』などと呼ばれる手遊びを知っていますか？その名称にピンとこなかったとしても，きっと，子供時代に幾度となく遊んだことがあるでしょう．

ここでは，『マッチ・グリーンピース・戦争』のルールを簡略化した手遊びを考え，『あれ』と名付けます．『あれ』は次のような2人プレイの遊びです．

(1)．各プレイヤーが両手の指を1本ずつ立てた状態から遊びを開始する．
(2)．先手のプレイヤーから順番に以下の(3)〜(5)を行う．
(3)．プレイヤーは，自身のどちらか一方の手で相手のどちらか一方の手に触れる．
(4)．触れられた手は，触れた手に立っている指の本数だけ追加で指を立てる．
    ここで，5本以上の指が立つべき状況になった手は退場する．
    （退場した手は，今後触れたり触れられるときに選ばれることはない．）
(5)．両手とも退場したプレイヤーがいるかどうか確認する．いるならば，両プレイヤーは(6)に従う．
(6)．遊びを終了する．このとき，少なくとも一方の手が残っているプレイヤーが勝者である．

磯野「よーし，僕からだね！」

おや？どうやら，磯野君が先手になったようですね．2人の遊びの行く末を見守ってみましょう．

磯野「じゃあ僕は，右手に2本，左手に1本ではじめるよ！」

中島「それなら僕は，右手に2本，左手に2本でいくよ！」

ちょっと待て，なんだそのルールは&minus;

どうやら，磯野君たちの間では，遊び開始時に各手に立っている指の本数を1 〜 4本のうち自由に決められるようです．ローカルルールってやつですね．

『あれ』のような類の遊びは，先手後手でどちらが必勝なのかを簡単に調べることができます．しかし，『あれ』に磯野君たちのローカルルールを取り入れると，先手後手の勝敗が変わってきそうです．とても気になりますね．皆さんも興味がおありなのでは？もしそうならば，実際に調査してみましょう．

磯野君と中島君がローカルルールを取り入れた『あれ』で遊ぶとします．磯野君が先手と仮定して，磯野君の左手にはL_i本，右手にはR_i本の指が，中島君の左手にはL_n本，右手にはR_n本の指が立っているとします．2人とも最適な行動を選択する場合，どちらが勝つかを判定してください．

入力形式

入力は以下の形式で与えられる．

L_i R_i
L_n R_n

1行目には磯野君の手の初期状態を表すL_i，R_iが空白区切りで与えられる．L_iは左手で立っている指の本数，R_iは右手で立っている指の本数である．

2行目には中島君の手の初期状態を表すL_n，R_nが空白区切りで与えられる．L_nは左手で立っている指の本数，R_nは右手で立っている指の本数である．

また，入力は以下の制約を満たす．

1 ≤ L_i, R_i, L_n, R_n ≤ 4

出力形式

磯野君が勝つ場合は“ISONO”を，中島君が勝つ場合は“NAKAJIMA”を1行に出力せよ．

入力例1

3 2
2 2

出力例1

NAKAJIMA

入力例2

3 2
2 3

出力例2

ISONO

入力例3

1 1
1 1

出力例3

NAKAJIMA

『あれ』は後手で常勝


Sample input:
3 2
2 2


Sample output:
NAKAJIMA

Submission status: Wrong Answer

Solution code:
L0, R0 = input().split()
L0 = int(L0)
R0 = int(R0)
L1, R1 = input().split()
L1 = int(L1)
R1 = int(R1)


def swap(a,b):#b = max
    if (a > b):
        tmp = a
        a = b
        b = tmp
    return a,b


while max(L0,R0)!=0 and max(L1,R1)!=0:
    L0,R0 = swap(L0,R0)
    L1,R1 = swap(L1,R1)
    atackmax = max(L0,R0)
    if atackmax + L1 >= 5:
        L1 = 0
    elif atackmax + R1 >= 5:
        R1 = 0
    elif atackmax + R1 < 5:
        if L0 != 0:
            if L1 == 0:
                R1 = R1 + L0
            else:
                L1 = L1 + L0
        else:
            if L1 == 0:
                R1 = R1 + R0
            else:
                L1 = L1 + R0
#    print(L0,R0)
#    print(L1,R1)

    if max(L1,R1) == 0:
        break

    L0,R0 = swap(L0,R0)
    L1,R1 = swap(L1,R1)

    
    atackmax = max(L1,R1)


    if atackmax + L0 >= 5:
        L0 = 0
    elif atackmax + R0 >= 5:
        R0 = 0
    elif atackmax + R0 < 5:
        if L1 != 0:
            if L0 == 0:
                R0 = R0 + L1
            else:
                L0 = L0 + L1
        else:
            if L0 == 0:
                R0 = R0 + R1
            else:
                L0 = L0 + R1
    if max(L0,R0) == 0:
        break
#    print(L0,R0)
#    print(L1,R1)
    #import pdb;pdb.set_trace()
if max(L0,R0)==0:
    print("NAKAJIMA")
elif max(L1,R1)==0:
    print("ISONO")

Submission status: Wrong Answer

Solution code:

Submission status: Accepted

Solution code:
def rec(li, ri, ln, rn, hand):
    if hand == 0:
        win = 1
        if li < 5:
            if ln < 5: win = min(win, rec(li, ri, li + ln, rn, 1 - hand))
            if rn < 5: win = min(win, rec(li, ri, ln, li + rn, 1 - hand))
        if ri < 5:
            if ln < 5: win = min(win, rec(li, ri, ri + ln, rn, 1 - hand))
            if rn < 5: win = min(win, rec(li, ri, ln, ri + rn, 1 - hand))
    else:
        win = 0
        if ln < 5:
            if li < 5: win = max(win, rec(li + ln, ri, ln, rn, 1 - hand))
            if ri < 5: win = max(win, rec(li, ri + ln, ln, rn, 1 - hand))
        if rn < 5:
            if li < 5: win = max(win, rec(li + rn, ri, ln, rn, 1 - hand))
            if ri < 5: win = max(win, rec(li, ri + rn, ln, rn, 1 - hand))
    return win
                
Li, Ri = map(int, raw_input().split())
Ln, Rn = map(int, raw_input().split())

print "ISONO" if rec(Li, Ri, Ln, Rn, 0) == 0 else "NAKAJIMA"

Submission status: Accepted

Solution code:
li, ri = map(int, input().split())
ln, rn = map(int, input().split())
ISONO = True
NAKAJIMA = False

def search(li, ri, ln, rn, turn):
  if li == None and ri == None:
    return False
  if ln == None and rn == None:
    return True

  if turn == ISONO:
    ret = False
    if li and ln:
      ret = ret or search(li, ri, ln + li if ln + li < 5 else None, rn, not turn)
    if li and rn:
      ret = ret or search(li, ri, ln, rn + li if rn + li < 5 else None, not turn)
    if ri and ln:
      ret = ret or search(li, ri, ln + ri if ln + ri < 5 else None, rn, not turn)
    if ri and rn:
      ret = ret or search(li, ri, ln, rn + ri if rn + ri < 5 else None, not turn)

  if turn == NAKAJIMA:
    ret = True
    if li and ln:
      ret = ret and search(li + ln if li + ln < 5 else None, ri, ln, rn, not turn)
    if li and rn:
      ret = ret and search(li + rn if li + rn < 5 else None, ri, ln, rn, not turn)
    if ri and ln:
      ret = ret and search(li, ri + ln if ri + ln < 5 else None, ln, rn, not turn)
    if ri and rn:
      ret = ret and search(li, ri + rn if ri + rn < 5 else None, ln, rn, not turn)

  return ret

if search(li, ri, ln, rn, ISONO):
  print("ISONO")
else:
  print("NAKAJIMA")

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>

using namespace std;
int ans = 1000;
bool dfs(int L0, int R0, int L1, int R1) {
	if (L1 >= 5 and R1 >= 5) { 
		return true;
	}

	if (R0 <= 4 and L1 <= 4 and !dfs(R0+L1,R1,L0,R0))return true;	
	if (R0 <= 4 and R1 <= 4 and !dfs(L1,R0+R1,L0,R0))return true;	
	if (L0 <= 4 and L1 <= 4 and !dfs(L0+L1,R1,L0,R0))return true;	
	if (L0 <= 4 and R1 <= 4 and !dfs(L1,R1+L0,L0,R0))return true;	
	else return false;
}


int main() {
	int L0,R0; cin >> L0 >> R0;
	int L1,R1; cin >> L1 >> R1;
	bool ans;
	ans = dfs(L0,R0,L1,R1);
	if (ans) {
		cout << "ISONO" << endl;	
	}else{
		cout << "NAKAJIMA" << endl;	
	}
	return 0;
}