トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ABC-055-C Scc Puzzle

■■■問題■■■

すぬけくんはパズルが好きです。

今日はSとcの形をしたピースを使ったパズルで遊んでいます。
このパズルでは図のようにc型のピースを2つ組み合わせてS型のピースを1つ作ることができます。

すぬけくんはS型のピースを1つ、c型のピースを2つ組み合わせて Sccという組を可能な限り多く作ることにしました。 すぬけくんがN個のS型のピースとM個のc型のピースを持っているとき、 Sccという組を最大でいくつ作ることが可能か求めなさい。

■■■入力■■■

N M

●1 <= N,M <= 1兆

■■■出力■■■

答えを出力せよ。


C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("1 6");
            //2
            //以下のような手順でピースを組み合わせることで
            //2つのSccという組を作ることが可能です
            //●c型のピース2つを組み合わせてSのピースを1つ作る
            //●S型のピース1つとcのピース2つを組み合わせてSccという組を1つ作る
            //●S型のピース1つとcのピース2つを組み合わせてSccという組を1つ作る
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("12345 678901");
            //175897
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();

        long CurrSCnt = wkArr[0];
        long CurrCCnt = wkArr[1];

        //手順1 Sとcのペアで、Sccを作れるだけ作る
        long CanCreateCnt1 = Math.Min(CurrSCnt, CurrCCnt / 2);
        CurrSCnt -= CanCreateCnt1;
        CurrCCnt -= CanCreateCnt1 * 2;

        //手順2 残ったcで、Sccを作れるだけ作る
        long CanCreateCnt2 = CurrCCnt / 4;

        Console.WriteLine(CanCreateCnt1 + CanCreateCnt2);
    }
}


解説

貪欲法で解いてます。