ARC126-A Make 10

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("3 4 1");
            WillReturn.Add("7 0 0");
            WillReturn.Add("0 0 7");
            WillReturn.Add("0 0 0");
            WillReturn.Add("1000000000000000 1000000000000000 1000000000000000");
            //2
            //1
            //0
            //0
            //900000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long Result = Solve_234_10(wkArr[0], wkArr[1], wkArr[2]);
            Console.WriteLine(Result);
        }
    }

    // 長さ(2,3,4)の個数を引数として
    // 長さ10の棒を何本作れるかを返す
    static long Solve_234_10(long pN2, long pN3, long pN4)
    {
        // mod 2で考えれば
        // 長さ3の棒は、必ず2つペアにして
        // 長さ6として使う必要あり
        long N6 = pN3 / 2;

        return Solve_123_5(pN2, pN4, N6);
    }

    // 長さ(1,2,3)の個数を引数として
    // 長さ5の棒を何本作れるかを返す
    static long Solve_123_5(long pN1, long pN2, long pN3)
    {
        long Answer = 0;

        // 最優先で作る 2の棒1本と、3の棒1本
        long MakePairCnt1 = Math.Min(pN2, pN3);
        Answer += MakePairCnt1;
        pN2 -= MakePairCnt1;
        pN3 -= MakePairCnt1;

        if (pN2 > 0) {
            // 2の棒2本と、1の棒1本
            long MakePairCnt2 = Math.Min(pN2 / 2, pN1);
            Answer += MakePairCnt2;
            pN2 -= MakePairCnt2 * 2;
            pN1 -= MakePairCnt2;

            // 2の棒1本と、1の棒3本
            long MakePairCnt3 = Math.Min(pN2, pN1 / 3);
            Answer += MakePairCnt3;
            pN2 -= MakePairCnt3;
            pN1 -= MakePairCnt3 * 3;
        }
        if (pN3 > 0) {
            // 3の棒1本と、1の棒2本
            long MakePairCnt4 = Math.Min(pN3, pN1 / 2);
            Answer += MakePairCnt4;
            pN3 -= MakePairCnt4;
            pN1 -= MakePairCnt4 * 2;
        }

        // 最後に残った1の棒5本
        Answer += pN1 / 5;
        return Answer;
    }
}

解説

長さ2,3,4で長さ10を作るので
mod 2 で考えれば、長さ3の棒は必ず2つ連結させると分かります。

長さ2,4,6で長さ10を作る問題になったので
全てを2で割って
長さ1,2,3で長さ5を作る問題に変更します。

オセロセットで試行錯誤すると
最優先で長さ2と長さ3を連結させて5を作る。

長さ1と長さ2が残った場合
長さ2*2と長さ1を作れるだけ作ってから
長さ2と長さ1*3を作れるだけ作る。

長さ1と長さ3が残った場合
長さ3と長さ1*2を作れるだけ作る。

最後に、長さ1*5を作れるだけ作る。

とするのが最適と分かります。