AOJ2024 Blackjack

問題リンク Blackjack

• 概要

ブラックジャックの得点を計算せよ。
ブラックジャックは手持ちのカードの点数の合計が得点になる。ただし21点を超えるようなものはbustと呼び、失格となる。
カードの数字は2〜9, T, J, Q, K, Aと表す。
2〜9はそれぞれ2〜9点。T, J, Q, Kは10点。Aは得点が21点により近づくように11点もしくは1点で加算する。
手持ちのカードが2枚で21点だと、blackjackと呼び、特別な役となる。
カードの山があり、以下のルールでカードを取るかどうかを決める。
1. 得点が16以下なら、カードを1枚とる
2. 得点がちょうど17で、11点と解釈されたAがあるならばカードを1枚とる
3. これら以外の場合、終了する
手持ちのカード2枚と、現在の山の上8枚の情報が入力で与えられる。

• 解法

実装問題です。基本的には上のルールをそのまま実装するだけです。
が、(かなり腑に落ちないんですけど)次のような決まりで得点を計算するようです。
Aが来た場合、それを11点とした場合と1点とした場合の両方を試し、結果が良かった方を採用するというのは間違いのようです。
正しくは、「Aを11点としたときに、bustすることなく終了するならばAは11点とする」です。これは、Aを1点としたときによりよい得点となろうが構わず一意に11点と決めるようです。気をつけましょう。

• ソース

import java.util.Scanner;

//Blackjack
public class AOJ2024 {

	char[] s;
	int res;
	boolean bj;
	
	int f(char c){
		if(Character.isDigit(c))return c-'0';
		return c=='A'?1:10;
	}
	
	boolean dfs(int k, int sum, boolean ace){
		if(21<sum)return false;
		if(sum<=16||sum==17&&ace){
			int x = f(s[k]);
			if(x==1){
				if(sum+11<=21)
					if(dfs(k+1, sum+11, true))return true;
				return dfs(k+1, sum+1, ace); 
			}
			else return dfs(k+1, sum+x, ace);
		}
		else{
			if(k==2&&sum==21)bj = true;
			if(sum<=21){
				res = Math.max(res, sum);
				return true;
			}
			return false;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			res = 0;
			bj = false;
			s = new char[10];
			for(int i=0;i<10;i++)s[i]=sc.next().charAt(0);
			boolean f = dfs(0, 0, false);
			System.out.println(bj?"blackjack":!f?"bust":res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2024().run();
	}
}