当前位置:首页 » Project Euler » 详细页

Darts 题号:109 难度: 45 中英对照

In the game of darts a player throws three darts at a target board which is split into twenty equal sized sections numbered one to twenty.


The score of a dart is determined by the number of the region that the dart lands in. A dart landing outside the red/green outer ring scores zero. The black and cream regions inside this ring represent single scores. However, the red/green outer ring and middle ring score double and treble scores respectively.

At the centre of the board are two concentric circles called the bull region, or bulls-eye. The outer bull is worth 25 points and the inner bull is a double, worth 50 points.

There are many variations of rules but in the most popular game the players will begin with a score 301 or 501 and the first player to reduce their running total to zero is a winner. However, it is normal to play a "doubles out" system, which means that the player must land a double (including the double bulls-eye at the centre of the board) on their final dart to win; any other dart that would reduce their running total to one or lower means the score for that set of three darts is "bust".

When a player is able to finish on their current score it is called a "checkout" and the highest checkout is 170: T20 T20 D25 (two treble 20s and double bull).

There are exactly eleven distinct ways to checkout on a score of 6:


D3

 

 
D1 D2  
S2 D2  
D2 D1  
S4 D1  
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

Note that D1 D2 is considered different to D2 D1 as they finish on different doubles. However, the combination S1 T1 D1 is considered the same as T1 S1 D1.

In addition we shall not include misses in considering combinations; for example, D3 is the same as 0 D3 and 0 0 D3.

Incredibly there are 42336 distinct ways of checking out in total.

How many distinct ways can a player checkout with a score less than 100?

Solution

题目告诉我们一共只有42336种方法完成游戏,因为我们可以使用暴力法(迭代所有情况)求解。 投一次可能的分数有 1-20 的一、二、三倍,加上两种 bulls eye,共62种可能。因为有doubles out的规则,最后一步的可能性共有1-20,25的双倍分数,共有21种。 规则要求投三次out,记D为双倍,S为命中,M为未命中,则成功out共分为三种情况:MMD、MSD、SSD。根据乘法原理和加法原理,所有可能的情况为: $$ 21 + 62\times21 + (\frac{62 \times 61}{2} \times 21 + 62 \times 21) = 42336 $$ 遍历所有情况,求满足三次总得分小于100的情况数即可。注意第三种情况下,10 20 D和20 10 D属性同一冲情况,在迭代时应注意。

Code

using System;
using System.Diagnostics;
using System.Collections.Generic;
namespace euler
{
	class Problem109
	{
		public static void Main(string[] args)
		{
			Stopwatch clock = Stopwatch.StartNew();
			var result = Run();
			clock.Stop();
			Console.WriteLine(result);
			Console.WriteLine("Solution took {0} ms", clock.Elapsed.TotalMilliseconds);
			Console.Read();
		}

		public static int Run()
		{
			int limit = 100;
			int result = 0;
			List<int> scores = new List<int>();
			//build all possible single dart scores
			for (int i = 1; i <= 20; i++)
			{
				scores.Add(i);
				scores.Add(2 * i);
				scores.Add(3 * i);
			}
			scores.Add(25);
			scores.Add(50);
			//make all the possible doubles
			List<int> doubles = new List<int>();
			for (int i = 1; i <= 20; i++)
			{
				doubles.Add(2 * i);
			}
			doubles.Add(25 * 2);
			//Count all miss, miss, double
			foreach (int i in doubles)
			{
				if (i < limit)
					result++;
			}
			//count all miss, hit, double
			for (int i = 0; i < scores.Count; i++)
			{
				foreach (int j in doubles)
				{

					if (scores[i] + j < limit)
						result++;
				}
			}
			//count all hit, hit, double            
			for (int i = 0; i < scores.Count; i++)
			{
				for (int j = i; j < scores.Count; j++)
				{
					foreach (int k in doubles)
					{
						if (scores[i] + scores[j] + k < limit)
							result++;
					}
				}
			}
			return result;
		}
	}
}
38182
Solution took 6.695 ms
import java.util.ArrayList;
import java.util.List;
public final class p109  {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    public static long run() {
        int limit = 100;
        int result = 0;
        List<Integer> scores = new ArrayList<>();
        //build all possible single dart scores
        for (int i = 1; i <= 20; i++){
            scores.add(i);
            scores.add(2 * i);
            scores.add(3 * i);
        }
        scores.add(25);
        scores.add(50);
        //make all the possible doubles
        List<Integer> doubles = new ArrayList<>();
        for (int i = 1; i <= 20; i++){    
            doubles.add(2 * i);
        }
        doubles.add(25 * 2);
        //Count all miss, miss, double
        for (int i : doubles) {
            if (i < limit){
                result++;
            }
        }
        //count all miss, hit, double
        for (int i = 0; i < scores.size(); i++) {
            for (int j : doubles) {
                if (scores.get(i) + j < limit){
                    result++;
                }
            }
        }
        //count all hit, hit, double
        for (int i = 0; i < scores.size(); i++) {
            for (int j = i; j < scores.size(); j++) {
                for (int k : doubles) {
                    if (scores.get(i) + scores.get(j) + k < limit){
                        result++;
                    }
                }
            }
        }
        return result;
    }
}
38182
15ms